Die Big Oh-Notation erwähnt keinen konstanten Wert

Ich bin Programmierer und habe gerade angefangen, Algorithmen zu lesen. Ich bin nicht ganz überzeugt von den Bezeichnungen Bog Oh, Big Omega und Big Theta. Der Grund ist laut Definition von Big Oh, dass es eine Funktion g (x) geben sollte, die immer größer oder gleich f (x) ist. Oder f (x) <= cn für alle Werte von n> n0.

Warum erwähnen wir den konstanten Wert in der Definition nicht? Nehmen wir zum Beispiel eine Funktion 6n + 4 an, die wir als O (n) bezeichnen. Aber es ist nicht wahr, dass die Definition für alle konstanten Werte gilt. Dies gilt nur, wenn c> = 10 und n> = 1. Für kleinere Werte von c als 6 erhöht sich der Wert von n0. Warum erwähnen wir den konstanten Wert nicht als Teil der Definition?

O (n) und andere Ordnungsnotationen beschäftigen sich (normalerweise) nicht mit dem Verhalten von Funktionen für kleine Werte. Es geht um das Verhalten von Funktionen für sehr große Werte, nämlich Grenzen, wenn n gegen unendlich geht.

Die Konstanten sind technisch gesehen von Bedeutung, werden jedoch in der Regel abstrahiert, sobald n groß genug ist, ist der Wert von c völlig irrelevant. Wenn der Wert von c wichtig ist, können wir ihn in die Analyse einbeziehen. Wenn jedoch die zu vergleichenden Funktionen sehr große konstante Faktoren aufweisen oder wenn die Effizienz ein besonders wichtiges Anliegen ist, ist dies normalerweise nicht der Fall.

Es gibt mehrere Gründe, aber der wahrscheinlich wichtigste ist, dass Konstanten eine Funktion der Implementierung des Algorithmus sind, nicht des Algorithmus selbst. Die Reihenfolge eines Algorithmus ist nützlich, um Algorithmen unabhängig von ihrer Implementierung zu vergleichen.

Die tatsächliche Laufzeit einer Quicksortierung ändert sich normalerweise, wenn sie in C oder Python oder Scala oder Postscript implementiert ist. Gleiches gilt für die Bubble-Sortierung - die Laufzeit variiert je nach Implementierung erheblich.

Was sich jedoch nicht ändert, ist die Tatsache, dass sich die für die Ausführung einer Blasensortierung erforderliche Zeit schneller erhöht, wenn der Datensatz größer wird, wenn alle anderen Werte gleich sind, und zwar unabhängig von Sprache oder Computer Sie werden unter der Annahme einer einigermaßen korrekten Implementierung mit implementiert. Diese einfache Tatsache ermöglicht es Ihnen, intelligente Rückschlüsse auf die Algorithmen selbst zu ziehen, wenn keine konkreten Details verfügbar sind.

Die Reihenfolge eines Algorithmus filtert Faktoren heraus, die zwar für Messungen in der realen Welt wichtig sind, beim Vergleich abstrakter Algorithmen jedoch nur zu Rauschen neigen.

Die Big-O-Notation nach Definition besagt Folgendes : Die Big-O-Notation basiert auf der Intuition, dass für alle Werte n an und rechts von n 'der Wert von f (n) auf oder unter cg (n) liegt. Die Konstanten spielen auch keine Rolle, wenn Sie zu höherwertigen (variablen) Faktoren (wie n-Quadrat oder n-Würfel) wechseln, da sie nur die Konstanten und nicht die variierenden Größen sind, die so groß werden können wie diese Faktoren. Unten ist das Diagramm der Big-O-Notation angegeben.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}

Das Wesentliche dieser Notation liegt in der Tatsache " how lower is f(n) from c.g(n) and not when it starts becoming lower".

In der Algorithmusanalyse ist die Reihenfolge des Wachstums die Schlüsselabstraktion und gibt die Rate an, mit der sich die Laufzeit ändert, wenn sich die Eingabegröße ändert. Angenommen, ein Algorithmus hat eine Laufzeit f(n) = 2n + 3. Jetzt schließen wir eine Eingabegröße an,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Wie zu sehen ist, wird die Wachstumsordnung hauptsächlich durch die Variable bestimmt n; Die Konstanten 2 und 3 sind weniger wichtig, und wenn die Eingabegröße zunimmt, werden sie bei der Bestimmung noch weniger wichtig. Aus diesem Grund werden in der Algorithmusanalyse Konstanten zugunsten der Variablen abgeklungen, die die Wachstumsordnung einer Funktion bestimmen.

(Da dies eine längere Antwort ist, lesen Sie die Fettschrift für eine Zusammenfassung. )

Lassen Sie uns Ihr Beispiel nehmen und Schritt für Schritt durchgehen, um den Zweck zu verstehen, der hinter dem steht, was wir tun. Wir beginnen mit Ihrer Funktion und dem Ziel, die Big Oh-Notation zu finden:

f(n) = 6n+4

Erstens lassen O(g(n))die Big Oh Notation wir zu finden versuchen f(n). Nach der Definition von Big Oh müssen wir eine vereinfachte g(n) Form finden, bei der es einige Konstanten gibt cund n0bei der c*g(n) >= f(n)gilt, dass alle ngrößer sind als n0.

Lassen Sie uns zuerst wählen g(n) = 6n + 4(was O(6n+4)in Big Oh ergeben würde ). In diesem Fall sehen wir, dass c = 1und jeder Wert von n0die mathematischen Anforderungen aus unserer Definition von Big Oh erfüllt, da g(n)immer gleich ist f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

Zu diesem Zeitpunkt haben wir die mathematischen Anforderungen erfüllt. Wenn wir bei stehen bleibenO(6n+4) , ist es klar, dass dies nicht hilfreicher ist als das Schreiben f(n). Es würde also den wahren Zweck der Big Oh-Notation verfehlen: die allgemeine zeitliche Komplexität eines Algorithmus zu verstehen! Fahren wir also mit dem nächsten Schritt fort: der Vereinfachung.

Erstens, können wir das 6nso vereinfachen, dass das große Oh ist O(4)? Nein! (Übung für den Leser, wenn er nicht versteht warum)

Zweitens können wir das vereinfachen, 4so dass das große Oh ist O(6n)? Ja! In diesem Fall g(n) = 6nalso:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

An dieser Stelle wählen wir, dass c = 2die linke Seite für jedes Inkrement von um 12 schneller (um 12) als die rechte Seite (um 6) ansteigt n.

2*6n      >=  6n + 4

Jetzt müssen wir ein Positiv finden, n0bei dem die obige Gleichung für alle gilt n, die größer als dieser Wert sind. Da wir bereits wissen, dass die linke Seite schneller wächst als die rechte, müssen wir nur eine positive Lösung finden. Da somit n0 = 2die oben wahr macht, wissen wir , dass g(n)=6n, oder O(6n)ist eine potentielle Big Oh Notation f(n).

Können wir das vereinfachen, 6damit das große Oh ist O(n)? Ja! In diesem Fall g(n) = nalso:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Wählen wir, c = 7da die linke schneller zunimmt als die rechte.

7*n         >=  6n + 4

Wir sehen, dass das oben Gesagte für alle gilt n, die größer oder gleich sind n0 = 4. Somit O(n)ist eine potenzielle Big Oh-Notation für f(n). Können wir noch vereinfachen g(n)? Nee!

Schließlich haben wir festgestellt, dass die einfachste Big Oh-Notation für f(n)ist O(n). Warum haben wir das alles durchgemacht? Weil wir jetzt wissen, dass dies f(n)linear ist , da die Big Oh-Notation von linearer Komplexität ist O(n). Das Schöne ist, dass wir jetzt die zeitliche Komplexität f(n)mit anderen Algorithmen vergleichen können! Zum Beispiel wissen wir jetzt , dass f(n)in vergleichbarer Zeit Komplexität der Funktionen ist h(n) = 123n + 72, i(n) = n, j(n) = .0002n + 1234, etc; da sie denselben oben beschriebenen Vereinfachungsprozess verwenden, haben sie alle eine lineare Zeitkomplexität von O(n).

Süss!!!

Wenn Sie eine Leistungsfunktion von haben 6n + 4, lautet die relevante Frage "6 was?". Als ein Kommentar gefragt: Was repräsentiert deine Konstante? Was sind physikalisch gesehen die Einheiten Ihres konstanten Faktors?

Der Grund, warum die O () - Notation so häufig zur Beschreibung der Algorithmusleistung verwendet wird, ist, dass es keine tragbare Möglichkeit gibt, diese Frage zu beantworten. Verschiedene Prozessoren benötigen eine unterschiedliche Anzahl von Taktzyklen und eine unterschiedliche Zeitdauer, um dieselbe Elementarberechnung durchzuführen, oder sie können die relevanten Elementarberechnungen unterschiedlich zusammenfassen. Unterschiedliche Computersprachen oder unterschiedliche formale und informelle Beschreibungen wie Pseudocode stellen Algorithmen auf eine Weise dar, die nur schwer direkt zu vergleichen ist. Sogar Implementierungen in derselben Sprache können denselben Algorithmus auf unterschiedliche Weise darstellen - triviale Formatierungsdetails wie die Anzahl der Zeilen stehen im Allgemeinen zur Verfügung, um einen beliebigen Algorithmus zu implementieren.

Anders ausgedrückt: Wir verwenden "Algorithmus" nicht, um eine bestimmte Implementierung zu beschreiben, sondern um eine ganze Klasse potenzieller Implementierungen derselben allgemeinen Prozedur zu beschreiben. Diese Abstraktion ignoriert die Details der Implementierung, um etwas von allgemeinem Wert zu dokumentieren, und der konstante Leistungsfaktor ist eines dieser Details.

Allerdings werden Algorithmusbeschreibungen häufig von Folklore, Notizen oder sogar tatsächlichen Benchmarks begleitet, die die Leistung tatsächlicher Implementierungen auf tatsächlicher Hardware beschreiben. Dies gibt Ihnen eine ungefähre Vorstellung davon, welche Art von konstantem Faktor zu erwarten ist. Sie sollten ihn jedoch auch mit einem Körnchen Salz einnehmen, da die tatsächliche Leistung davon abhängt, wie viel Arbeit in die Optimierung einer bestimmten Implementierung gesteckt wurde. Langfristig tendiert die relative Leistung vergleichbarer Algorithmen dazu, sich zu ändern, wenn sich die Architektur der neuesten und größten Prozessoren ändert ...

Der gesamte Begriff der Big-Oh-Notation besteht darin, Konstanten zu ignorieren und den wichtigsten Teil der Funktion darzustellen, die die Laufzeit eines Algorithmus beschreibt.

Vergiss die formale Definition für einen Moment. Welches ist die schlechtere (schneller wachsende) Funktion n^2 - 5000oder 5000 n + 60000? Für nweniger als 5000 ist die lineare Funktion größer (und damit schlechter). Darüber hinaus (genauer Wert 5013?) Ist die quadratische Gleichung größer.

Da es mehr (ziemlich viele mehr) positive Zahlen gibt, die größer als 5000 sind, nehmen wir das Quadrat als die "größere" (schlechtere) Funktion im Allgemeinen. Die Ordnungsnotation (Big-Oh usw.) erzwingt dies (Sie können mit diesen Definitionen immer einen Zusatz und eine multiplikative Konstante eliminieren).

Natürlich sind die Dinge nicht immer einfach. Manchmal muss man tun will , dass diese Konstanten kennen. Was ist besser Einfügung sortieren oder Bubble sortieren? Beides sind O(n^2). Aber einer ist wirklich besser als der andere. Mit einer ausführlicheren Analyse können Sie Konstanten erhalten, über die Sie sich wundern. Normalerweise ist es viel einfacher, die Big-Oh-Funktion zu berechnen, als eine genauere Funktion.

Big-Oh ignoriert diese Konstanten, um die wichtigsten Vergleiche zu vereinfachen und zu vereinfachen. Wir mögen die Notation, weil wir normalerweise nichts über die (meist irrelevanten) Konstanten wissen wollen.