Summe Regel für BIG-O mit gleichen Komplexitätsfunktionen?

Question

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 $ g_1 $ und $ g_2 $ , dann ist die kombinierte Komplexität $ f_1 + f_2= o (\ max (g_1, g_2)) $ .

Aber was wählen wir, wenn beide Komplexitätsfunktionen gleich sind? Wenn $ F_1 (n) $ die Sortierung eines Arrays und $ _ f2 (m) $ ist Dann sind auch die Komplexität $ O (n \ log (n)) $ und $ o (m \ log ( m)) $ . Die Anwendung der Regel wäre $ o (\ max (n \ log (n), m \ log (m))) $ . Ich denke, dass die Auswahl eines davon eine gültige, aber uneingeschränkte Schätzung ergeben würde, da Sie eine Variable fallen würden. Außerdem ist es nicht klar, was man auswählt.

ist es der Fall, dass Sie die Regel nicht verwenden sollen, wenn mehrere Variablen beteiligt sind?

Answer 1

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 $ m \ times n $ Matrix und einen $ n \ Male P $ Matrix nimmt $ o (MNP) $ -time mit der Schulbuchvervielfachung oder der Lösung des Rucksackproblems nimmt $ o (NT) $ < / span> -time wo $ n $ ist die Anzahl der Elemente und $ T $ ist die Zielsumme .

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 $ o (n ^ 2 \ log n) $ , was besser ist als Floyd-Warshall. Beachten Sie dagegen, dass Dijkstra in $ M \ log n $ für den allgemeinen Fall, das auf dichtem Diagramm ist, in denen $ bedeutet M= O (N ^ 2) $ , es wird weniger effizient als Floyd-Warshall in Bezug auf die schlimmste Laufzeit.

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 $ .

Answer 2

Es gibt keine allgemeine Antwort.Wenn Sie den $ O (\ max (n \ \ log (n), m \ log (m \ m))) $ , können Sie neu schreibenes als $ o ((n + m) \ log (n + m)) $ .

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))) $ .

Answer 3

per Definition $ o (g) $ sollte immer definierter variabler und limitspunkt in Bezug auf $ o $ . In $ o (n ^ 3) ist n \ to \ inmTy $ variable $ n $ und Begrenzungspunkt $ \ Infty $ . In $ o (x ^ 3) ist x \ bis 0 $ variable $ x $ und Grenzwert $ 0 $ .

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 $$ F_1 (n) + F_2 (n)= o (\ max (g_1, g_2) (n)), n \ bis \ fly $$ Oder wir brauchen mehr Klarstellung in Bezug auf Variablen, vorausgesetzt den Grenzpunkt $ \ Infty $ .