Effizienz von Sortieralgorithmen

Question

Ich studiere für ein ziemlich wichtiges Interview morgen und es gibt eine Sache, die ich sehr viel Mühe habe, mit:. Sortieralgorithmen und BIGO Effizienz

Welche Zahl ist wichtig zu wissen? Die beste, am schlechtesten, oder durchschnittliche Effizienz?

Answer 1

Schlimmste, von durchschnittlich gefolgt. der reale Welt Auswirkungen des sogenannten „hidden Konstanten“ zu bewusst sein - zum Beispiel, ist der klassische quicksort Algorithmus O (n ^ 2) im schlimmsten Fall, und O (n log n) im Durchschnitt, während mergesort O (n log n) im schlimmsten Fall, aber quicksort mergesort in der Praxis übertrifft.

Answer 2

Sie sind alle wichtig zu wissen, natürlich. Sie müssen die Vorteile eines Sortieralgorithmus im durchschnittlichen Fall verstehen allerdings nicht Defizit im schlimmsten Fall werden kann, oder im schlimmsten Fall ist nicht so schlimm, aber der beste Fall ist nicht so gut, und es funktioniert nur gut auf unsortierte Daten etc.

Answer 3

Kurz gesagt.

Sortieralgorithmus Effizienz auf Eingangsdaten und Aufgabe variiert.

• max Geschwindigkeit Sortierung, die archiviert werden kann, ist n * log (n)
• , wenn Daten sortierten Unterdaten enthält, können max Geschwindigkeit besser dann n * log (n)
• , wenn Daten von Duplikaten bestehen, Sortierung kann in nahezu linearer Zeit
erfolgen
• die meisten Sortieralgorithmen haben ihren Nutzen

Die meisten schnell sortieren Varianten haben ihren durchschnittlichen Fall auch n * log (n), aber deine sind in der Regel schneller als andere nicht stark optimierte Algorithmen. Es ist schneller, wenn es nicht stabil ist, aber stabile Varianten sind nur ein Bruchteil langsamer. Hauptproblem ist schlimmster Fall. Beste lässig fix ist Introsort.

Die meisten Mergesort Varianten haben ihre besten, mittleren und schlechtesten Fall n * log feste (n). Es ist stabil und relativ leicht zu skalieren. Aber es braucht einen Binärbaum (oder deren Emulation) mit im Verhältnis zur Größe der Gesamtzahl der Elemente. Das Hauptproblem ist die Erinnerung. Beste lässig fix ist Timsort.

Sortieralgorithmen unterscheiden sich auch nach der Größe der Eingabe. Ich kann einen Neuling Anspruch geltend machen, dass über den Eingang 10T Größendaten, da für Mergesort Varianten keine Übereinstimmung gibt.

Answer 4

Ich empfehle, dass Sie nicht nur diese factoids merken. Erfahren Sie, warum sie sind, was sie sind. Wenn ich Sie interviewte, würde ich sicherstellen, dass Fragen zu stellen, die zeigen, meinen Sie verstehen, wie einen Algorithmus zu analysieren, nicht nur kann spucken wieder aus etwas, das Sie auf einer Webseite oder in einem Buch gesehen. Darüber hinaus ist der Tag vor einem Interview nicht die Zeit, das Studium zu tun.

Ich wünsche Ihnen viel Glück !! Bitte melden Sie in einem Kommentar zurück, wie es ist!

Answer 5

Ich bin über mit einem Satz von Interviews an meiner Hochschule gerade jetzt ...

Jeder Algorithmus hat seine Vorteile, sonst wird es nicht existieren. Also, es ist besser zu verstehen, was mit dem Algorithmus so gut ist, dass Sie studieren. Wo tut es gut? Wie kann sie verbessert werden?

Ich denke, Sie werden automatisch verschiedene Effizienz Notationen lesen müssen, wenn Sie dies tun. Achten Sie auf den schlimmsten Fall ist, und achten Sie auf den durchschnittlichen Fall, sind am beste Fälle selten.

Alles Gute für Ihr Interview.

Answer 6

Sie können auch in andere Arten sehen mögen, dass die Sortierung kann verwendet werden, wenn bestimmte Bedingungen erfüllt sind. Betrachten wir zum Beispiel Radix sortieren. http://en.wikipedia.org/wiki/Radix_sort