Komplexität eines Algorithmus abschätzen

[Alexander]

Hallo,
ich habe schon öfter Komplexitätsangaben von veschiedenen (Sortier-) Algorithmen gesehen.
Mich würde mal interessieren, wie man die abschätzen kann, ohne groß zu rechnen und Messungen durchzuführen. Es soll dann natürlich nur eine ungefähre Angabe sein.
Bei den Sortieralgorithmen gibt es ja im Prinzip zwei Gruppen, die mit einer logarithmischen und einer quadratischen Komplexität.
Mich würde das einfach mal interessieren ;)

[shmia]

Zitat:

Zitat von Alexander

ich habe schon öfter Komplexitätsangaben von veschiedenen (Sortier-) Algorithmen gesehen.
Mich würde mal interessieren, wie man die abschätzen kann, ohne groß zu rechnen und Messungen durchzuführen. Es soll dann natürlich nur eine ungefähre Angabe sein.
Bei den Sortieralgorithmen gibt es ja im Prinzip zwei Gruppen, die mit einer logarithmischen und einer quadratischen Komplexität.

Es gibt mehr "Gruppen":

Code:

linear:          O(N)=N
logarithmisch:   O(N)=N*Log(N)
quadratisch:     O(N)=N*N
kubisch(*):      O(N)=N^3
potenziert(*):   O(N)=2^N
fakultät(*):     O(N)=N!

die Bezeichnungen mit dem * habe ich erfunden.
In der O-Schreibweise bezeichnet das Argument N die Anzahl der Eingangsdaten und O(N) ist
annähernd proportional der Laufzeit.
Man kann jetzt nicht behaupten, dass ein quadratischer Algo schneller als ein logarithmischer ist,
aber bei grossen Werten von N wird der logarithmische besser abschneiden.

[Alexander]

Hi, gibt es einen linearen Sortieralgo ? Sortieralgorithmen sind nicht ganz so mein Gebiet ;)

Kannst du mir auch noch sagen, wie man jetzt ungefähr die Komplexität eines unbekannten Algos abschätzen kann. Mich interessiert das nur mal...
Wäre super nett von dir ;)

[Phoenix]

Zitat:

Zitat von Alexander

Hi, gibt es einen linearen Sortieralgo ? Sortieralgorithmen sind nicht ganz so mein Gebiet ;)

Wenn Du einen findest bist Du reich: Quicksort ist derzeit der schnellste bekannte Sortieralgoritmus und hat loragrithmische Komplexität.

Allerdings kannst Du mit linearem Aufwand feststellen, ob etwas sortiert ist oder nicht.

[LarsMiddendorf]

Radix Sort sortiert mit linearem Aufwand. Allerdings nicht durch Vertauschen oder Vergleichen, sondern die Position eines Elementes wird direkt errechnet, was ja zumindest bei Zahlen nicht weiter schwer aber auch nicht wirklich nützlich ist.
Beim Sortieren durch Vergleichen und Vertauschen ohne zusätzlichen Speicher kann man glaube ich auch Beweisen, dass es keinen schnelleren Algorithmus geben kann. Ich glaube der Beweis geht so, dass man für jedes Element einen binären Entscheidungsbaum aufstellt, der dann natürlich eine Tiefe von log(n), also log(n) Entscheidungen, enthält und das ganze dann n Mal durchgeführt wird.

[Nikolas]

Die einfachsten Algos. also Selection und Insection sind doch linear.
Für jedes Element mehr, musst du einmal mehr über die noch vorhandenen Elemente laufen.

[stoxx]

Zitat:

Wenn Du einen findest bist Du reich: Quicksort ist derzeit der schnellste bekannte Sortieralgoritmus und hat loragrithmische Komplexität.

Das stimmt wohl so glaub ich nicht ganz 100 prozentig.
Laut einem schlauen Algorithmen Buch, in dem ich mal gelesen hatte, kann man Quicksort noch optimieren, wenn man zum Ende der Sortierung auf einen anderen Algorithmus wechselt.
(genaueres habe ich nicht untersucht, wäre mir für Standardaufgaben auch der Aufwand nicht wert ;-)
Quicksort hat den Vorteil, dass es die Elemente über "große Reichweiten" transportieren kann.
Auch in dem besonderen Falln, wenn Du schon eine fast sortierte Datenmenge vorliegen hast, ist Quicksort auch fehl am Platz.

[Tubos]

Zitat:

Laut einem schlauen Algorithmen Buch, in dem ich mal gelesen hatte, kann man Quicksort noch optimieren, wenn man zum Ende der Sortierung auf einen anderen Algorithmus wechselt.

Das ist nichts neues.
Wird in Daniels Suchalgorithmen-Tutorial auch erwähnt.
Man sortiert per QuickSort, und gegen Ende sortiert man den Rest mit Insertion Sort, dadurch kann man das Ganze nochmal beschleunigen.

[stoxx]

Zitat:

Mich würde mal interessieren, wie man die abschätzen kann, ohne groß zu rechnen und Messungen durchzuführen. Es soll dann natürlich nur eine ungefähre Angabe sein.

Hallo Alex,

um Deine Grundfrage zu beantworten, irgendwo in der Mitte steht wohl was genaueres über Deine Frage :-)

http://www.sts.tu-harburg.de/~r.f.mo...rlesung-17.pdf

[Alexander]

Zitat:

Zitat von stoxx

Zitat:

Mich würde mal interessieren, wie man die abschätzen kann, ohne groß zu rechnen und Messungen durchzuführen. Es soll dann natürlich nur eine ungefähre Angabe sein.

Hallo Alex,

um Deine Grundfrage zu beantworten, irgendwo in der Mitte steht wohl was genaueres über Deine Frage :-)

http://www.sts.tu-harburg.de/~r.f.mo...rlesung-17.pdf

Danke habe mir die SEiten gerade durchgelesen. Da kann ich schon was mit anfangen.
Wenn ihr noch mehr Infos habt, dann nur her damit ;)

Zitat:

Zitat von Phoenix

Wenn Du einen findest bist Du reich: Quicksort ist derzeit der schnellste bekannte Sortieralgoritmus und hat loragrithmische Komplexität.

Allerdings kannst Du mit linearem Aufwand feststellen, ob etwas sortiert ist oder nicht.

Habe ich mir nämlich schon gedacht, daher die Frage ;). Mir waren nämlich auch die logarithmischen Sortieralgos Merge- und Quicksort bekannt.