Zählen Sie die Anzahl der Vorgänge für einen Sortier-Algorithmus
Dies ist meine Aufgabe Frage:
Erklären Sie mit einem Beispiel quick-sort , merge-sort und heap-sort .
weiter zählen der Anzahl von Operationen, die von jedem dieser Sortier-Methoden.
Ich verstehe nicht, was genau ich habe, zu beantworten, im Rahmen von "count die Anzahl der Operationen" ?
Fand ich etwas in coremen Buch in Kapitel 2, Sie haben erklärt, Insertionen Sortieren die Laufzeit eines Algorithmus durch die Berechnung der Laufzeit einer jeden Aussage ....
habe ich zu tun, die in ähnlicher Weise ?
Sie benötigen, um zu bestimmen, Ihre Komplexität (entweder worst-case oder average case)
InformationsquelleAutor Tony | 2010-09-05
Du musst angemeldet sein, um einen Kommentar abzugeben.
Zum zählen der Anzahl von Operationen ist auch bekannt als
analysieren Sie den Algorithmus Komplexität
. Die Idee ist, haben eine grobe Idee, wie viele Operationen sind im worst-case benötigt, um führen Sie den Algorithmus auf einer Eingabe der Größe N, die Ihnen die Obere Grenze der rechnerischen Ressourcen, die erforderlich sind für diesen Algorithmus. Und da jeder Betrieb für sich (wie Multiplikation oder Vergleich zum Beispiel) ist eine endliche operation und dauert deterministische Zeit (obwohl es möglicherweise unterschiedliche, auf verschiedenen Rechnern), um eine Idee zu bekommen, wie gut oder schlecht ein Algorithmus ist, vor allem im Vergleich zu anderen algorithmen, alles, was Sie wissen müssen, ist die grobe Anzahl von Operationen.Hier ist ein Beispiel mit bubble-sort. Lassen Sie uns sagen, Sie haben ein array von zwei zahlen. Sortieren Sie vergleichen müssen beide zahlen und möglicherweise austauschen. Da der Vergleich und Austausch sind die einzigen Operationen, die genaue Zeit für die Ausführung ist minimal und nicht wichtig ist, von selbst. Somit kann man sagen, dass mit N=2, die Anzahl der Operationen ist O(N)=1. Für drei zahlen, obwohl, müssen Sie drei Operationen in der worst-case - vergleichen Sie die erste und die zweite und möglicherweise austauschen, vergleichen Sie dann die zweite und die Dritte und austauschen, dann vergleichen Sie die erste mit der zweiten erneut. Wenn Sie weiter die Verallgemeinerung der bubble-sort, werden Sie feststellen, dass potentiell zum Sortieren von N zahlen, die Sie benötigen, zu tun N Operationen für die erste Zahl, N-1 für die zweite und so weiter. In anderen Worten, O(N) = N + (N-1) + ... + 2 + 1 = N * (N-1) /2, die für groß genug, N vereinfacht sich dies zu O(N) = N^2.
Natürlich, Sie könnten nur betrügen und informieren Sie sich auf den web-O(N) Anzahl für jede der drei sort-algorithmen, aber ich möchte Sie bitten, die Zeit zu verbringen und versuchen, sich mit dieser Nummer selbst auf den ersten. Auch wenn Sie es falsch ist, vergleichen Sie Ihre Schätzung ist und wie Sie es mit der tatsächlichen Art und Weise zu schätzen, Ihre Komplexität wird Ihnen helfen, besser zu verstehen, den Prozess der Analyse der Komplexität von bestimmten Stück software, die Sie schreiben in Zukunft.
InformationsquelleAutor Franci Penov
Genannt wird big O-notation.
Diese Seite zeigt Ihnen die gängigen Sortier-algorithmen und deren Vergleich, ausgedrückt durch big O.
Vom http://www.softpanorama.org/Algorithms/sorting.shtml
InformationsquelleAutor Leniel Maccaferri
Ich denke, dass diese Zuordnung ist, um Ihnen eine Idee geben, wie die Komplexität eines Algorithmus berechnet wird. Zum Beispiel bubble-sort-Algorithmus hat eine Komplexität von O(n^2).
Wie Sie oben sehen, sind zwei ösen für die Sortierung des Arrays. Lassen Sie ARRAY_SIZE n. Dann die Anzahl der Operationen ist n*(n-1). Das macht n^2-n ist gekennzeichnet durch O(N^2). Das ist big O-notation. Nehmen wir nur das n mit dem größten Exponenten, die höchste Wachstumsrate. Wenn es 2n^2+2n, wäre das immer noch O(N^2), da die Konstanten sind ebenfalls nicht in die Berechnung der Komplexität. Der wikipedia-Artikel über Big O-Notation ist wirklich hilfreich (wie Leniel erwähnt in seinem post).
Dass Sie Ihre Hausaufgaben, so dass ich nicht bekommen, in die details der algorithmen, die Sie erwähnt. Aber Sie müssen die Mathematik zu tun, wie diese. Aber ich denke, dass Sie gefragt werden, was ist die tatsächliche Anzahl von Operationen. Also, für das Beispiel oben, wenn ARRAY_SIZE 10 ist, lautet die Antwort bekommt 10*9=90. Um die Unterschiede zu sehen, müssen Sie das gleiche array in deinem Beispiel-codes.
InformationsquelleAutor Zafer