Wie lautet eine einfache englische Erklärung der "Big O"-Notation?

Question

Ich bevorzuge so wenig formale Definitionen wie möglich und einfache Mathematik.

Answer 1

Nur um die Komplexität eines Algorithmus auf schnelle und einfache Weise auszudrücken. Die Big-O-Notation dient dazu, die beste, die schlechteste und die durchschnittliche Zeitkomplexität für einen beliebigen Algorithmus anzugeben. Es handelt sich lediglich um numerische Funktionen über die Größe möglicher Probleminstanzen.

Andererseits ist es sehr schwierig, mit diesen Funktionen präzise zu arbeiten, da sie dazu neigen:

• Zu viele Unebenheiten haben - Ein Algorithmus wie die binäre Suche läuft normalerweise etwas schneller für Arrays der Größe genau n = 2k 1 (wobei k eine ganze Zahl ist), weil die Array-Partitionen gut funktionieren. Dieses Detail ist nicht besonders wichtig, aber es warnt uns davor, dass die genaue Zeitkomplexitätsfunktion für jeden Algorithmus sehr kompliziert sein kann, mit kleinen Ausschlägen nach oben und unten, wie in Abbildung 2.2 gezeigt.
• Erfordert zu viele Details, um sie genau zu spezifizieren - Zählung der genauen Anzahl der im schlimmsten Fall ausgeführten RAM-Befehle zu zählen, muss der Algorithmus Algorithmus bis ins Detail eines vollständigen Computerprogramms spezifiziert werden. Außerdem hängt die genaue Antwort von uninteressanten Codierungsdetails ab (hat er z. B. eine Case Anweisung oder verschachtelte ifs?). Die Durchführung einer genauen Worst-Case-Analyse wie T(n) = 12754n2 + 4353n + 834lg2 n + 13546 wäre zweifellos eine sehr schwierige Aufgabe, die uns aber kaum mehr Informationen liefert als die Feststellung, dass "die Zeit quadratisch mit n wächst".

Es erweist sich als viel einfacher, in Form von einfachen Ober- und Untergrenzen zu sprechen von Zeitkomplexitätsfunktionen zu sprechen, wenn man die Big-Oh-Notation verwendet. Das Big Oh vereinfacht unsere Analyse, indem wir Detailstufen ignorieren, die keinen Einfluss auf den Vergleich der Algorithmen auswirken. Die Big-Oh-Notation ignoriert den Unterschied zwischen multiplikativen Konstanten. Die Funktionen f(n)=2n und g(n) = n sind in der Big-Oh-Analyse identisch

https://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaDerAlgorithmusDesignMan ual.pdf