Also ich weiß, dass die Effizienz durch die in einer Lösung verwendeten Algorithmen und Datenstrukturen bestimmt wird. Aber ich verstehe nicht wirklich, wie die Reihenfolge eines Algorithmus wichtiger ist als die Geschwindigkeit des Prozessors?Warum ist die Reihenfolge eines Algorithmus im Allgemeinen wichtiger als die Geschwindigkeit des Prozessors?
Ein typischer PC kann 10^8 calculations per second.
Und der schnellste Supercomputer der Welt tut .
Angenommen, Sie haben gerade einen O (n) -Algorithmus auf Ihrem Laptop/Desktop ausgeführt. Und ein O (n^2) -Algorithmus, der gleichzeitig auf dem schnellsten Supercomputer der Welt läuft. Und wenn n = 10^10,
Laufzeit auf dem PC = 10^10/10^8 = 100 seconds.
Laufzeit auf dem Supercomputer = 10^20/10^16 = 10000 seconds.
So deutlich übertrifft der Laptop den Supercomputer mit großem Vorsprung. Und ist tatsächlich 100 mal schneller, während es nur einen besseren Algorithmus verwendet. Ein anderer Grund, warum wir nach besseren Algorithmen suchen, ist das scalability Problem. Nach moore's law, verdoppelt sich die Rechenleistung alle 18 Monate. Selbst wenn ein Supercomputer heute sehr schnell mit sehr großen Eingaben umgehen kann, wird er dies möglicherweise später nicht mehr tun können, wenn sich die Problemgröße um ein Vielfaches erhöht hat, während sich die Rechenleistung in den nächsten 18 Monaten nur verdoppelt hätte.
Die Taktgeschwindigkeit, die Sie für den Supercomputer angegeben haben, setzt natürlich voraus, dass der Algorithmus die parallele Architektur voll ausnutzen kann. –
@TimBiegeleisen \t Ja, das weiß ich. Ich denke nur an die schlimmsten Fälle, um das OP von den Vorteilen eines besseren Algorithmus zu überzeugen. –
Diese Antwort setzt voraus, dass O (n^2) n^2 bedeutet. 0,1 n^2 und 1000 n^2 + 10^100 sind beide O (n^2).Ich bin überrascht, dass Sie das Mooresche Gesetz als eine Art Hinweis darauf anführen, dass die Rechenleistung mit der Zeit langsam zunimmt. Normalerweise wird Moores Gesetz aus dem entgegengesetzten Grund zitiert. –
man kann nicht sagen Reihenfolge eines Algorithmus ist mehr/weniger wichtig als CPU-Geschwindigkeit !!! Sie sind nicht vergleichbar !!!! verwenden wir Befehle, um verschiedene Algorithmen miteinander zu vergleichen, da wir die Zielarchitektur, die der Algorithmus ausführt, nicht kennen. Als eine weitere Anmerkung hängt die Ausführungszeit eines Programms von vielen Faktoren wie Cach-Miss-Rate, Hauptspeichertreffer-Verhältnis und .... ab, so dass die Ausführungszeit in jedem Ausführungsprogramm von vorherigen abweichen kann. als Ergebnis können wir zwei Programme nicht vergleichen, indem Sie sie auf einer Struktur ausführen !!!
Ich versuche, auf eine einfache Art zu erklären.
Die Prozessorgeschwindigkeit wird in Zyklen/Sek. Gemessen und variiert von Prozessor zu Prozessor. Um einen Algo zu beurteilen, brauchen wir eine davon unabhängige, auf dem Algo basierende Metrik.
Nehmen wir an, dass eine einzelne Operation in einem Algorithmus einen Prozessorzyklus erfordert. Also, für die Reihenfolge von algo n, wenn Eingabe von Größe n ist, sind n Prozessorzyklen erforderlich. Wenn die Reihenfolge algo n^2 ist, sind n^2 Prozessorzyklen erforderlich, wenn die Eingangsgröße n ist.
Sie sehen also, die Reihenfolge eines Algorithmus ist eine Metrik unabhängig von der Prozessorgeschwindigkeit. Je niedriger die Reihenfolge, desto schneller funktioniert es.
Dies ist eine sehr allgemeine Antwort, aber ich hoffe, es löscht Ihre Zweifel.
auf ein Beispiel Werfen wir einen Blick:
Sie haben einen Algorithmus mit einer Größenordnung von O (n^3). Sie führen diesen Algorithmus auf einem Prozessor aus, der in 100 Millisekunden n = 10 verarbeiten kann.
Wenn n zu 10000 geht, benötigt dieser Prozessor 1158 Tage.
Einen Prozessor doppelt so schnell zu bekommen, würde das nur auf 579 Tage reduzieren.
Selbst wenn Sie einen Prozessor zehnmal so schnell bekommen könnten, würde es noch Monate dauern.
Aber durch Ersetzen dieses Algorithmus mit einem der Ordnung von O (n^2) und das Ausführen auf dem ursprünglichen Prozessor würde die benötigte Zeit auf 2,8 Stunden reduzieren.
besser als angenommene Antwort –
Ob es wichtiger ist, hängt von der Situation ab. Die Komplexitätsreihenfolge eines Algorithmus ist nicht direkt mit seiner Geschwindigkeit verknüpft. Es kann "schlechtere" Algorithmen geben, die eine bestimmte Probleminstanz schneller lösen als ein "besserer" Algorithmus. Wie von den anderen Antworten erklärt, kommt die Komplexitätsreihenfolge auf die Frage "Wie wächst Speicher/Zeitverbrauch mit Eingabegröße?". Für kleine Eingaben ist es egal. Für durchschnittliche Eingaben vergleichen Sie Ihre Algorithmen und sehen, welche auf Ihrer Hardware schneller läuft. Das Problem sind unerwartet große Eingaben: Jetzt interessiert es dich, ob zehnfache Daten zehnfache Knirschenzeit, hundertfache Wartezeit oder endlose Berechnung bis zum Hitzetod des Universums bedeuten.
Ein prominentes Beispiel dafür ist die Windows XP update mechanism. Sie verarbeiten die Liste der installierten Updates mit einem Algorithmus mit exponentieller Laufzeit. Dies war kein Problem und lief akzeptabel schnell, bis - Jahrzehnte später - die Anzahl der Updates ein echtes Problem machte.
Aber als Computerwissenschaftler habe ich eine andere Sicht auf, was wichtiger ist: Algorithmische Komplexität ist viel interessanter. Einen Algorithmus mit besserer Komplexität herauszufinden, ist ein intellektuelles Problem. Wenn Sie nur für schnellere Ergebnisse interessiert sind, können Sie Ihre Hardware genauso einfach aufrüsten. Sie können Rechenleistung für Geld bekommen. Die Geschwindigkeit der Prozessoren verbessert sich mehr oder weniger - holen Sie sie einfach und beschleunigen Sie Ihr Programm [1]. Bis Sie die Grenze (der Technologie oder des Budgets) erreicht haben, und Sie brauchen einen besseren Algorithmus. Dann hast du eine richtige Nuss zum knacken. Ein Denkfehler. Was ist purer Spaß!
1: Ich sage nicht, dass Prozessoren schnell zu machen trivial ist. Aber sie zu verwenden, um Probleme zu lösen, ist :-)
Ich glaube Reihenfolge bezieht sich auf [Big O] (http://en.m.wikipedia.org/wiki/Big_O_notation), in welchem Fall der Grund a (Big O) Reihenfolge ist wichtiger für die Leistung ist einfach Ausführen des Algorithmus verwendet weniger Schritte. –
Es ist nicht. Ich führe Algorithmen mit einem exponentiellen Worst-Case bei relativ großen Eingaben mit Gleichmäßigkeit durch. – tmyklebu
Ich denke, die stärkste Aussage, die gemacht werden kann, ist, dass für ausreichend große * n * die Reihenfolge eines Algorithmus wichtiger für die Leistung ist als die Geschwindigkeit des Prozessors. In vielen realen Szenarien ist jedoch * n * nicht groß genug, um den Algorithmus niedrigerer Ordnung tatsächlich schneller zu machen, und es gibt andere praktische Überlegungen, wie die Einfachheit und Wartbarkeit des Codes, der den Algorithmus implementiert. Diese Frage hat daher keine klare Antwort und wird zu Meinungen und Diskussionen einladen. – njuffa