Asymptotische Notation - nicht n (log n) (log n) vereinfachen?

Question

Wenn ich einen Algorithmus, der n log nimmt n Schritte (zB Heapsort), wobei die Schritte unternehmen, um log n Zeit (zB Vergleichs- / Austausch von „großen“ ganze Zahlen im Bereich von 0 bis n-1), was die asymptotisch ist gebunden für den gesamten Prozess.

Natürlich können wir sagen, „n (log n) (n log)“, aber ich habe eine harte Zeit versucht, mich davon zu überzeugen, dass ich dies nicht vereinfachen kann „n log n“. Zur gleichen Zeit, habe ich eine harte Zeit den Instinkt zu rechtfertigen, die darauf besteht, dass ich es kann.

Ist mein Instinkt einfach falsch auf das?

Bearbeiten

Es scheint, mein einfach Beispiel zu vermeiden verkomplizieren um die Frage, die Frage kompliziert ist. Na gut.

Der wahre Grund für die Frage ist, dass ich oft einen Standard-Algorithmus mit einer bekannten Komplexität, aber unterschiedliche zugrunde liegenden Container implementiert, so dass die einzelnen Schritte sind O (log n) anstelle von O (1). Zum Beispiel ist Hopcrofts Automat Minimierungsalgorithmus O (n log n) - aber wenn Sie mit binären Baum Container für die Zustände, Übergänge und Zwischenergebnisse beginnen, sich die Schritte werden O (log n) - die O (n log n) ist nicht mehr gültig, da die Annahme von O (1) zugreift, ist ungültig.

Dennoch werden die Leute behaupten, dass es n Zustände und m Übergänge, wobei n und m sind in der Regel linear für Automaten bezogen werden, unter der Annahme, dass die Anzahl der Übergang Anmerkungen konstant ist und dass die Automaten sind mehr oder weniger deterministisch.

Ich habe nicht zu viel über diese in der Vergangenheit besorgt - die Fälle, mit denen ich arbeite sind nicht sehr groß. Aber, na ja, ich bin eine große Refactoring meiner Automaten Code zu tun, und ich dachte, ich könnte genauso gut die Mathematik tun richtig für einige Schlüsselalgorithmen, wie ich gehe.

Bearbeiten

Ich bin auch immer mehr davon überzeugt, dass die "n (log n) (log n)" ist falsch.

Wenn ein O (b log b) wobei b O (log c) ist, was für eine in Bezug auf die c?

Answer 1

Hier ist ein Beweis durch Widerspruch:

Nehmen wir an, dass eine Funktion f (n) = n (log n) (log n). Nehmen wir an, wir denken, es ist auch Theta (n log n), so in anderen Worten, es ist ein ein, für die f (n) <= a * n log n für große n gilt.

f (2 ^ (a + 1)) betrachten

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), die deutlich größer ist als a * 2 ^ (a + 1) * log (2 ^ (a + 1)), und wir haben einen Widerspruch . also f (n) kein n log n Funktion.

Answer 2

In der Regel können Sie nicht Komplexitäten wie folgt multiplizieren: für die Stapelsortier, zeigt N die Anzahl der Elemente in dem Haufen, während für die großen Zahlen, wahrscheinlich N die obere Grenze der möglichen Werte anzeigt. Im Allgemeinen sind diese nicht in Beziehung gesetzt werden müssen, so dass es eher ist N log N log M (wobei M die Strecke ist, dass die Elemente dauern).

In einer speziellen Anwendung höchstwahrscheinlich folgen die großen ganzen Zahlen einige spezifische Verteilung. Zum Beispiel kann es bekannt sein, dass sie alle unter 10 ^ 20 sind. Wenn dem so ist, haben die Vergleichsoperationen konstante Zeit (bestimmt durch eine obere Grenze von 10 ^ 20). Dann log M ist ebenfalls konstant, und die gesamte Komplexität ist in O (N log N).

Answer 3

Sie können reduzieren n (log n) (log n) nicht einfach n (log n), denn das ist nicht eine Reduktion um einen konstanten Faktor.

Was ist los mit n (log n) 2 ?

Answer 4

Okay, die allgemeine Komplexität Maßnahme eines Programms ist die folgende:

  

Komplexität O (f (n)) bedeutet, dass es c vorhanden ist, so dass die Anzahl der entsprechenden Turing Maschinenschritte, bevor es beendet wird, nicht mehr als c * f (n), wobei n die Länge der Eingabe ist.

In dieser Definition wird alles berücksichtigt, weil die ganzen Zahlen beliebig groß sein können, und arithmetische Operationen an sie würden auch die Funktion unter O (n) erhöhen.

Wenn wir aber Turing-Maschinen wurden direkt programmieren, Ihre Frage wäre entstanden ist, wurde nicht. In der realen Welt bevorzugen wir abstrahieren. Während wir noch „Stufen“ berechnen, die benötigt werden, um das Programm auszuführen, gehen wir davon aus, dass bestimmte Operationen nehmen einen Schritt . Wir gehen davon aus, dass durch verschiedene Gründe:

• Es kann die eigentliche Arbeit des CPU ähnelt, wobei jede 32-Bit-Integer-Addition ist in der Tat ein Schritt (und es existiert Algorithmen, die es tatsächlich missbrauchen, zum Beispiel „Bit-verctor dominators“).
• Wir vergleichen verschiedene Algorithmen in derselben Domäne (zB Vergleich Array Sortierungen durch die Anzahl der Vergleiche Messung).

In diesem Fall (Ihre erste EDIT), wenn Sie Ihre Komplexität Maßnahme konkretisieren wollen, sollten Sie nur Funktionen unter O. multiplizieren Wenn das, was Sie einen Schritt nehmen dachte jetzt nehmen O betrachtet (log N) Schritten, dann ist die Menge an konkretisierten Schritten erhöht sich um einen Faktor O (log N). Deshalb ist die Gesamtkomplexität O (N log N log N).

---

In Bezug auf Ihre zweite EDIT, es ist eine andere Situation. Lassen Sie Ihren Algorithmus eine Komplexität von O sein (n log N). Aber Sie wissen, dass die Eingabe besteht aus M Zahlen, die jeweils log K Ziffern, so `N = O (M log K) (wir müssen Separatoren berücksichtigen, etc). Es ist mathematisch korrekt dann die Gesamtkomplexität zu schreiben, wie O (M * K * log (log M + log K log)), so gibt es hier kein Problem. Aber in der Regel abstrakt wir weg unnötige Details, eine gemeinsame Basis zu finden verschiedene Algorithmen verglichen werden.