Summe Regel für BIG-O mit gleichen Komplexitätsfunktionen?
-
29-09-2020 - |
Frage
Eine Eigentum der Big-o-Notation ist der Summenregel , was Gibt an, dass, wenn ich zwei Funktionen habe $ F_1 $ und $ F_2 $ und ihre entsprechenden Komplexitätsfunktionen sind
Aber was wählen wir, wenn beide Komplexitätsfunktionen gleich sind? Wenn
ist es der Fall, dass Sie die Regel nicht verwenden sollen, wenn mehrere Variablen beteiligt sind?
Lösung
Es hängt davon ab, ob einige Variablen an einem anderen abhängig sind oder wenn sie als Parameter im Problem angegeben sind. Beispielsweise kann in vielen grafischen Problemen, $ n $ die Anzahl der Scheitelpunkte sein, und $ M $ kann die Anzahl der Kanten sein. In diesem Fall kann $ M $ so groß wie $ O (n ^ 2) $ sein. Sagen Sie also im allgemeinen Fall, wenn wir einen Algorithmus haben, dessen erste Phase in $ O (n) $ und zweiter Phase in $ O (m) $ , wir fügen einfach die beiden Bedingungen zusammen und versuchen nicht, zu vereinfachen --- Die endgültige Laufzeit ist $ O (n + m) $ .
In Bezug auf mehrere Variablen, die als Parameter angegeben sind, die nicht unbedingt verwandt sind: Mehrere Variablen in der Endgleichung ist Standard, z. Ich kann sagen, dass das Multiplizieren eines
In besonderen Fällen wie planare Grafiken und andere spärliche Grafiken wissen wir, dass $ M= O (n) $ , so dass wir $ n $ anstelle von $ M $ in der endgültigen Laufzeit zur Vereinfachung.
als digressesion, dies zeigt, warum auf sparsamen Grafiken (wobei $ m= o (n) $ ) man lieber Dijktra in einer Schleife für alle verwenden würde. Paar kürzester Pfad (im Gegensatz zu einem transitiven Schließkörper-basierten Algorithmus wie Floyd-Warshall); Da jetzt Dijkstra in $ O (m \ log n)= o (n \ log n) $ , läuft, wird die gesamte Komplexität für die Verwendung von Dijkstra in einer Schleife
In anderen Fällen können verschiedene Variablen vorhanden sind, nicht sogar in einem bestimmten Parameter polynomisch begrenzt sind - - Nehmen Sie das obige Rucksack-Beispiel oben, wobei $ T $ sein kann Exponential in $ N $ .
Andere Tipps
Es gibt keine allgemeine Antwort.Wenn Sie den
außerdem, wenn $ g_1 $ und $ g_2 $ sind EQAUL und zunehmende Funktionen, die Sie schreiben können $ o (g_1 (n + m)) $ anstelle von $ o (\ max (g_1 (n), g_2 (g_1 (n), g_2 (m))) $ .
per Definition $ o (g) $ sollte immer definierter variabler und limitspunkt in Bezug auf $ o $ . In
Wenn wir also $ f= o (g) $ schreiben, dann meinen wir formal eine variable und ein gewisser Grenzpunkt. Beispielsweise ist $ F (n)= o (g (n)), n \ to \ inmTy $ genaue Datensatz. HINWEIS, diese Datensatz $ F (m)= o (g (m)), m \ bis \ inmTy $ bedeutet genau wie früherer Satz.
Wenn wir über die Eigenschaft $ F_1 + F_2= O sprechen (\ max (G_1, G_2)) $ , dann sollte hier auch einige variable (s ) und etwas Grenzwert. So genaue Rekord sollte so etwas sein