Warum beschuldigen Sie nicht Ihre Probleme für die Ungenauigkeit der O-Ratings?

    Die jüngste Veröffentlichung dieses und jenes hat mich dazu inspiriert, diesen Beitrag zu schreiben.Übersetzungen, in denen Autoren in intelligenter Form ihre Unzufriedenheit darüber zum Ausdruck bringen, wie O-Schätzungen der rechnerischen Komplexität scheinbar klassischer Algorithmen mit ihrer praktischen Entwicklungserfahrung in Konflikt gerieten. Hauptkritikpunkt war das Speichermodell, in dessen Rahmen diese Schätzungen gewonnen wurden - es berücksichtigt die Besonderheiten der hierarchischen Organisation durch das in modernen Rechnersystemen vorkommende Geschwindigkeitsprinzip nicht. Daraus erwachsen alle folgenden Probleme. Und der beobachteten Reaktion dankbarer Leser nach zu urteilen, sind die Autoren keineswegs allein in ihrer Empörung und ihrem Wunsch, den Klassikern mit ihren O-Bigs "zu begegnen". Vielleicht lohnt es sich also wirklich, die Geschichten der Onkel in weißen Kitteln, die sie für lampenweise langsam denkende Autos angefertigt haben, auf die Mülldeponie zu bringen.

    Haben Sie die Konstante in O-groß berücksichtigt?

    Verstehen wir das.

    Im Verlauf des Textes werde ich auf die zweite Veröffentlichung und einige Kommentare dazu verweisen . Berührt für die Lebenden. Aber lassen Sie uns zunächst einmal vereinbaren, was im Verlauf dieses Textes verstanden wird.

    Wir führen die Definition ein. Sei und sei zwei reelle Funktionen, die am Set definiert sind . Dann wird der Datensatz zeigt an, dass es eine positive Zahl ist , so dass für alle wahr . Eine solche Bezeichnung wird -notation genannt, und O wird Bachmann-Symbol oder einfach " O- large" genannt.

    Aus dieser Definition hat es sofort mehrere Konsequenzen:

    1. Wenn alle halten , dann" следует, что . В частности, имеем, что умножение на константу не меняет O-оценку.

    Проще говоря, при умножении O-выражения на константу символ Бахмана эту константу «съедает». Это означает, что знак равенства в выражении, включающем в себя O-оценку, нельзя интерпретировать как классическое «равенство» значений и к таким выражениям нельзя применять математические операции без дополнительных уточнений. В противном случае мы бы получили странные вещи по типу следующей: . Это следствие произвольности константы, которая «прячется» за символом Бахмана.

    2. Если ограничена на , то есть существует такое число , что для всех Es wird ausgeführt , dann .

    Aus dem Mathematischen ins Russische zu übersetzen und der Einfachheit halber das endliche Intervall der Zahlengeraden zu nehmen, ergibt sich folgendes: Wenn eine Funktion in einem gegebenen Intervall nicht unendlich ist, ist das Bedeutungsloseste, was darüber gesagt werden kann, dass es O (1) entspricht. . Dies sagt nichts Neues über ihr Verhalten aus .

    Errate meine Komplexität
    Die blaue Linie ist O (√N).

    Kehren wir zum Fall der Abschätzung der Komplexität des Algorithmus zurück und sehen wir uns das Bild des Autors der zitierten Veröffentlichung an. Unter Berücksichtigung einer Verlängerung der Ausführungszeit wird der Schluss gezogen, dass die Schätzung von O (1) insolvent ist. Das Intervall, in dem das Verhalten des Programms analysiert wird, ist jedoch endlich. Tatsächlich wird behauptet, die Schätzung O (1) sei schlecht.

    Nun ... danke, Cap.

    Außerdem wird weiter versucht zu raten ! Die majorisierende Funktion ist einfach in Form einer Kurve, sie sagen "so wie es aussieht". Berücksichtigen Sie, ohne den Algorithmus selbst zu analysieren, die Funktionen, auf die er sich konzentrieren möchte, und führen Sie kein Speichermodell ein! Und warum gibt es eigentlich eine Quadratwurzel und keine kubische? Oder ist es nicht eine Art Logarithmus? Naja, richtiges Wort, sie würden wenigstens ein paar Möglichkeiten bieten, warum dann sofort "Aufmerksamkeit, die richtige Antwort"?

    Hier lohnt sich eine Reservierung. Natürlich führe ich nicht zu falschen Schlussfolgerungen, dass sich die Zugriffszeit verkürzt, wenn Sie vom Prozessor auf ein „weiter entferntes“ Laufwerk wechseln. Aber der Zeitpunkt des Empfangs eines Teils der Daten für willkürlichDer Zugriff auf den Speicher selbst auf der langsamsten Ebene der Hierarchie ist ein konstanter Wert oder zumindest begrenzt. Daraus folgt die Schätzung O (1). Und wenn es nicht begrenzt ist und von der Dimension der Daten abhängt, dann ist der Zugriff auf den Speicher nicht willkürlich. Also per definitionem dumm . Vergessen wir nicht, dass es sich um idealisierte algorithmische Konstrukte handelt. Wenn also gesagt wird, dass "Rechenzentren über die Festplatte hinausgehen" ... Meine Herren, welche Art von wahlfreiem Zugriff ist dies, welche Arrays und Hash-Tabellen? Dies nennt man einen Schwindel unter dem Tisch: Sie ändern leise die Bedingungen der Aufgabe, bringen die Antwort auf die vorherige und rufen: „Ahtung! Falsch wie! " Es verursacht für mich einen Anfall von schwerer Ratlosigkeit. Immerhin, wenn das Wort Array , Vektor oder <irgendein Typ> *Ihr Compiler verbirgt beispielsweise ein Stück Speicher, das über die Knoten eines Clusters verteilt ist - es kann alles in der Struktur sein, aber kein Array im Sinne von Wirth- und Knuth-Büchern, und Sie können die Ergebnisse der formalen Analyse, die in diesen Büchern geschrieben wurden, auf eine sehr dumme Idee anwenden. Und nicht weniger Schizophrenie - sprechen Sie im Ernst über die Gemeinsamkeit der Bewertung, die anhand eines Diagramms mit den Ergebnissen eines willkürlichen Tests erstellt wurde.

    Der Irrtum des gegebenen Urteils liegt in der Tatsache, dass die O- Bewertung der Komplexität auf der Grundlage des Experiments erfolgt. Um dies zu betonen, führen wir eine weitere Eigenschaft der O- Notation ein, die auf Schätzungen der algorithmischen Komplexität anwendbar ist:

    3. OEine Bewertung kann nur aus der Analyse der Struktur des Algorithmus erhalten werden, nicht jedoch aus den Ergebnissen des Experiments. Nach den Ergebnissen des Experiments ist es möglich, statistische Schätzungen, Expertenschätzungen, ungefähre Schätzungen und schließlich technische und ästhetische Vergnügen zu erhalten - jedoch keine asymptotischen Schätzungen.

    Letzteres ist eine Folge der Tatsache, dass die eigentliche Bedeutung solcher Schätzungen darin besteht, eine Vorstellung vom Verhalten des Algorithmus für ausreichend große Werte zu erhaltenDatenabmessungen und wie groß ist in der Regel nicht angegeben. Dies ist nicht das einzige und bei weitem nicht immer wichtigste, aber interessante Merkmal des Algorithmus. In den Tagen von Dijkstra und Hoar konnten die Ordnungen der Dimensionen 3-6 als ziemlich groß angesehen werden, heutzutage 10-100 (nach meinen Schätzungen, die nicht die Tiefe der Analyse vorgeben). Mit anderen Worten, die Frage nach der Erlangung asymptotisch Schätzungen Funktion Komplexität des Algorithmus erhöhen, ist es zweckmäßig , die Definition zu ändern O -notatsii so: Es

    sei . Dann heißt es , dass es voneinander unabhängige positive Zahlen A und n gibt , so dass für alle gilt .

    Das heißt, bei der Analyse der algorithmischen Komplexität betrachten wir tatsächlich Majoranten der Komplexitätsfunktion für alle links und nicht rechts begrenzten Intervalle. Dies bedeutet, dass solche O- Schätzungen beliebig oft angegeben werden können und alle derartigen Schätzungen praktisch nützlich sein können. Einige von ihnen sind für kleine N genau , gehen aber schnell ins Unendliche. Andere werden langsam wachsen, aber sie werden fair sein, beginnend mit einem solchen N , zu dem wir auf unseren elenden Computern gerne zum Mond laufen. Also, wenn wir davon ausgehen, dass die Schätzung der Zugriffszeit auf den SpeicherWenn eine Strukturanalyse ausgeblendet ist, könnte diese Schätzung in einem bestimmten Bereich von Dimensionen verwendet werden, aber selbst dann hätte sie die Genauigkeit der Schätzung O (1) nicht aufgehoben.

    Ein klassisches Beispiel für einen falschen Vergleich von asymptotischen Schätzungen sind Quadratmatrix-Multiplikationsalgorithmen. Wenn wir eine Wahl zwischen den Algorithmen nur auf der Grundlage eines Vergleichs der Schätzungen treffen, nehmen wir den Williams-Algorithmus und sorgen uns nicht. Sie können demjenigen nur kreativen Erfolg wünschen, der sich entschlossen hat, ihn auf die Matrizen von Dimensionen anzuwenden, die für technische Probleme charakteristisch sind. Andererseits wissen wir, dass ab einer bestimmten Dimension des Problems der Strassen-Algorithmus und seine verschiedenen Modifikationen schneller funktionieren als der triviale, und dies gibt uns Handlungsspielraum bei der Auswahl von Lösungsansätzen.

    Wie Dummheit von Intelligenz kommt


    Die Ungenauigkeit von O- Ratings zu sündigen bedeutet, die Bedeutung dieser Schätzungen nicht vollständig zu verstehen, und wenn dies der Fall ist, zwingt sie niemand zur Verwendung. Es ist durchaus möglich und oft gerechtfertigt, statistische Schätzungen zu bevorzugen, die als Ergebnis von Tests an für Ihre Region spezifischen Datensätzen erhalten wurden. Der Analphabetismus eines solch empfindlichen Instruments als asymptotische Analyse führt zu Exzessen und allgemein überraschenden Dingen. Beispielsweise können Sie mit O -Notation die Inkonsistenz der Idee der parallelen Programmierung "" beweisen.

    Nehmen wir an, unser Algorithmus, dem ein Datenblock der Dimension N zugeführt wird und der komplex ist, wenn er sequentiell ausgeführt wird , einfach und ohne Einschränkung in dasselbe Nunabhängig und der Einfachheit halber Teile der gleichen rechnerischen und zeitlichen Komplexität. Wir bekommen, dass die Komplexität jedes solchen Teils ist . Angenommen, wir haben M unabhängige Taschenrechner. Dann ist die Gesamtkomplexität der Ausführung eines parallelen Algorithmus nichts anderes als. Es stellte sich heraus, dass sich die asymptotische Abschätzung der Komplexität des Algorithmus nicht ändert, wenn er auf eine endliche Anzahl von Prozessen perfekt parallelisiert wird. Der aufmerksame Leser bemerkte jedoch, dass sich die „versteckte“ Konstante, die das Bachmann-Symbol aufgehämmert hatte, geändert hatte. Das heißt, es ist zumindest albern, aus einer solchen Analyse allgemeine Schlussfolgerungen zu ziehen, die sich auf die Idee der Parallelisierung beziehen. Es ist aber auch ein anderes Extrem möglich - zu vergessen, dass die Anzahl der Prozessoren natürlich und auf der Grundlage einer unendlichen Ressource der Parallelität O (1) ist.

    Um es zusammenzufassen


    Abschließend können Sie die folgenden attraktiven Neuheitsaussagen machen:

    • Es kann nicht argumentiert werden, dass ein Algorithmus effizienter ist als ein anderer, basierend auf einem einfachen Vergleich ihrer O- Schätzungen. Eine solche Aussage bedarf immer der Erklärung.

    • Es ist unmöglich, aus den Ergebnissen von Leistungsmessungen auf die Richtigkeit oder Unrichtigkeit solcher Schätzungen zu schließen - die versteckte Konstante ist normalerweise unbekannt und kann recht groß sein.

    • Sie können (und müssen manchmal) über Algorithmen und Datenstrukturen sprechen, ohne solche Schätzungen zu verwenden. Geben Sie dazu einfach an, für welche spezifischen Eigenschaften Sie sich interessieren.

    • Es ist jedoch besser, spezifische technische Entscheidungen zu treffen und dabei unter anderem die Merkmale der verwendeten Algorithmen zu berücksichtigen.

    Die Behauptung, dass die asymptotischen Schätzungen ungenau, falsch oder unpraktisch sind, wird häufig durch die Zurückhaltung bei der Durchführung einer normalen vorläufigen Analyse des gestellten Problems und den Versuch, sich auf den Namen zu stützen, aber nicht auf das Wesentliche der behandelten Abstraktionen, verdeckt. Wenn man von der asymptotischen Komplexität des Algorithmus spricht, versteht ein kompetenter Spezialist, dass es sich um idealisierte Konstruktionen handelt, den Grad der Richtigkeit der Projektion auf echte „Hardware“ im Auge behält und vom Wort „allgemein“ niemals ausschließlich darauf beruhende technische Entscheidungen trifft. O.-Auswertungen sind nützlicher, wenn neue Algorithmen entwickelt und grundlegende Lösungen für komplexe Probleme gefunden werden, und sie sind weniger nützlich, wenn bestimmte Programme für eine bestimmte Hardware geschrieben und getestet werden. Wenn Sie sie jedoch falsch interpretiert haben und überhaupt nicht das erhalten haben, was Ihnen Ihr Verständnis für das, was Sie in intelligenten Büchern gelesen haben, versprochen hat, müssen Sie zugeben, dass dies kein Problem für diejenigen ist, die Beweise für diese Bewertungen erhalten haben.

    Jetzt auch beliebt: