Ich hätte ziemlich allgemeine Frage. Mussten Sie jemals wirklich (z. B. auf dem Papier) die Komplexität eines Algorithmus berechnen, außer in der Schule als Programmierer? Und wenn ... kannst du mir bitte ein Beispiel geben.Komplexität des Algorithmus
danke :)
Ich weiß nicht, ob Sie mit der Programmierung Wettbewerbe als Schule betrachten oder nicht, sondern um zu sehen, wenn Sie einen Wettbewerb Problem (mit den angegebenen Problemgröße Einschränkungen) in der Frist nicht lösen können, Sie müssen die Anzahl der Operationen grob schätzen, indem Sie die Komplexität des verwendeten Algorithmus berücksichtigen.
Wenn Sie ein Stück Software schreiben und sich mehrere Möglichkeiten vorstellen, es zu implementieren, ist oft die algorithmische Komplexität einer der entscheidenden Faktoren (neben der konzeptionellen Komplexität und der Implementierungszeit). Wenn also Ihr Chef eine Rechtfertigung für Ihre Entscheidung benötigt, ist es notwendig, die Komplexität jedes einzelnen herauszufinden. Während einige dies als eine Form der vorzeitigen Optimierung betrachten, glaube ich, dass die Wahl eines Designs, das für Ihr Problem geeignet ist, nur eine gute Softwareentwicklung ist.
Bei der Arbeit diskutieren wir beiläufig variierende Algorithmen, um ein Problem zu lösen, und Komplexität spielt ihre Rolle. Es ist nie etwas, wo wir strenge Beweise der Komplexität machen müssen, sondern nur ein generelles "wir könnten X machen, aber das wäre O (N^2), was zu viel ist, weil wir über Millionen von Reihen iterieren könnten."
Überoptimierung kann zu schlechtem Code führen, aber die Komplexität Ihres Basisalgorithmus zu kennen, ist ein langer Weg, um den besten Weg zur Lösung eines Programmierproblems zu finden.
Natürlich! Jedes Mal, wenn Sie etwas über eine Million Mal tun, sollten Sie Ihren Algorithmus überprüfen.
Eine Instanz, die ich gemacht habe, war, als ich Millionen von Bildern erzeugte, die in ein Rastermuster passen mussten. Entschuldigung - kann nicht viel spezifischer für diesen einen bekommen.
Absolut - wir hatten erst kürzlich ein Problem mit unserer App, wo es plötzlich einige große Verlangsamungen zu schlagen begann. Es stellte sich heraus, dass wir einen kubischen (O (n^3)) Algorithmus genau in der Mitte einer sehr wichtigen Funktion hatten. Es war unter Schichten von Abstraktion versteckt worden. Um herauszufinden, was passiert war, musste das Funktionsaufrufdiagramm abgebildet und die Details betrachtet werden.
Zugegeben, sobald wir das getan haben, ist es nicht so, dass ich irgendeine Mathematik anwenden müsste, um einen O (n^3) -Algorithmus zu bemerken, aber das liegt hauptsächlich daran, dass mir 3 Jahre Analyse von Algorithmen an der Universität ein allgemeines Gefühl gegeben hat wie ein kubischer Algorithmus aussieht.
Wie auch immer, es stellte sich heraus, dass N nur ein kleines bisschen zugenommen hatte, aber es war an der Schwelle von ein paar hundert Millisekunden zu ein paar Sekunden und dann in Minuten - so hatte das Problem nicht gezeigt bis vor kurzem.
In den meisten Fällen werden Sie vorgefertigte Algorithmen mit definierten Komplexitäten verwenden. Quicksort ist O (n^2) schlechtester Fall und O (n * log (n)) durchschnittlicher Fall, binäre Suche ist O (log (n)), etc. Bibliotheken geben im Allgemeinen an, was ihre Leistungsmerkmale sind, und nur Sie müssen sich darum sorgen, wie sie komponieren.
Ja.
Im Allgemeinen ist die Komplexität offensichtlich genug für Serviettendarstellungen, und das ist gut für die Entwicklung, bis ich an den Punkt komme, an dem ich die Leistung messen muss. In vielen Fällen ist der Abschnitt, um den ich mir Sorgen gemacht habe, in Ordnung (dh, die Schätzung der Serviette war gut genug) und etwas anderes verlangsamt die Software. In fast allen Fällen lohnt es sich, mit meinen Grundannahmen zu gehen und später die Leistung zu messen.
Wenn ich jedoch sehr zeitkritischen Code mache, insbesondere im Grafik-Rendering, setze ich mich hin und ermittle die Komplexität des Algorithmus und die damit verbundenen Kompromisse auf eine andere Art und Weise.
Heute arbeite ich mit jemand anderem Code und es ist schrecklich langsam. Es interessiert mich nicht wirklich - es kann 10 Minuten dauern, bis alles, was für den gesamten Prozess wichtig ist, verbessert wird. Aber ich musste mir den Code ansehen, um einen Fehler zu beheben, und diese Person hat Schleifen innerhalb von Schleifen innerhalb von Schleifen, die meisten von ihnen durchsuchen die gleiche Liste jedes Mal auf die gleiche Weise für ein anderes Element. Im Grunde ist er ein schönes arrayfunction geändert, sagen func (i) {return Datensätze [i];} in eine schreckliche Suchroutine:
func(i)
{
for each index in records
if i==index return records[index]
next
}
Die Realität ist viel schlimmer, aber Sie bekommen die Idee.
Der Grund, warum Sie dies jetzt in der Schule lernen, ist, dass Sie diese Strukturen sehen und automatisch kategorisieren können. Du wirst wahrscheinlich nicht wirklich Computer brauchen oder es auf eine nette, ordentliche Komplexitätszahl reduzieren, aber wenn du es jetzt nicht mit der Hand machst und viel davon siehst, wirst du auch Code wie diesen produzieren und du wirst es einfach tun keine Ahnung haben.
-Adam
Ich weiß nicht, dass ich die Dinge tatsächlich aufzuschreiben, aber die ganze Zeit ich beurteilen, wie ich meine Algorithmen bin konstruieren, um zu sehen, ob ich die Effizienz der es verbessern kann. Bei Code frage ich mich, ob es eine Möglichkeit gibt, verschachtelte Schleifen in eine einzelne Schleife zu verwandeln oder von einer Schleife in die Verwendung eines Divide and Conquer-Ansatzes. Dies würde äquivalent dazu sein, von O (N) zu O (N) und O (N) zu O (log N) zu gehen. Gleiches gilt für SQL - kann ich einen Join entfernen und eine Unterabfrage anstelle eines Indexes ausführen - vielleicht von O (N) nach O (N) (oder sogar O (1), wenn es mir ermöglicht, zu indizieren) Abfragen in beiden Tabellen).
Ja und nein.
Ich schrieb ein Tool, um RPM-Abhängigkeiten einer Reihe von Paketen in eine einzige Kette zu reduzieren. Die offensichtliche Lösung lief zu langsam, also durchforstete ich meine Erinnerung ein wenig, um mich an einen O(n+m) Algorithmus aus der Graphentheorieklasse zu erinnern. Ich habe eine kleine Rückumschlag-Berechnung durchgeführt, um sicherzugehen, dass es wirklich O(n+m) war, dann schrieb ich es und steckte es in die Produktion :)
Hast du ein Beispiel für das SQL, das du erwähnst? Weil Joins mit Indizes und Unterabfragen ungefähr gleichwertig sind (oft wird eines mit dem anderen implementiert) – Javier
Ich dachte nicht wirklich an ein bestimmtes Beispiel, nur an den allgemeinen Prozess. – tvanfosson
Mit SQL könnte es so einfach sein, zu bemerken, dass das Hinzufügen eines Index es erlauben würde, einen anderen Algorithmus zu verwenden, der effizienter wäre. – tvanfosson