Sind 2 ^ n und n * 2 ^ n gleichzeitig komplex?

178

Ressourcen, die ich zur Zeitkomplexität gefunden habe, sind unklar, wann es in Ordnung ist, Begriffe in einer Zeitkomplexitätsgleichung zu ignorieren, insbesondere bei nichtpolynomiellen Beispielen.

Mir ist klar, dass bei etwas in der Form n 2 + n + 1 die letzten beiden Begriffe unbedeutend sind.

Ist bei zwei Kategorisierungen, 2 n und n * (2 n ), die zweite in derselben Reihenfolge wie die erste? Ist die zusätzliche n-Multiplikation dort wichtig? Normalerweise sagen Ressourcen einfach, dass x n exponentiell ist und viel schneller wächst ... dann fahren Sie fort.

Ich kann verstehen, warum dies nicht der Fall ist, da 2 n n deutlich übertreffen wird, aber da sie nicht addiert werden, wäre es beim Vergleich der beiden Gleichungen von großer Bedeutung. Tatsächlich wird der Unterschied zwischen ihnen immer ein Faktor von n sein. das scheint gelinde gesagt wichtig zu sein.

algorithm big-o complexity-theory time-complexity matty-d
quelle
8
Angesichts der Tatsache, dass NLogN streng langsamer als N angesehen wird, aber die meisten Menschen sich nicht wirklich darum kümmern, wie viel, ist es meiner Meinung nach sicher zu sagen, dass N2 ^ N einfach langsamer als 2 ^ N ist, aber für Menschen nicht "langsamer genug" zu kümmern ..
Jack
@tobias_k, ich verstehe diesen Punkt, aber betrachte das Beispiel von O (n!). Wäre ein zusätzlicher n-Begriff wirklich anders? O (n!) Ist zu O (n * n!) Wie O (n!) Zu O ((n + 1)!), Auch bekannt als derselbe Graph, der einfach verschoben wurde. Das Wachstum ist jedoch das gleiche ... Ist das Wachstum in diesem Fall unterschiedlich, obwohl man streng groß ist? Ist das nicht die Zeitkomplexität?
Matty-D
3
@ JackWu, aber die meisten Leute kümmern sich nicht wirklich darum, um wie viel, bis Sie Hunderte Millionen Datensätze mit nlogn anstelle von n sortieren müssen :)
CB
4
Das n! = o((n+1)!)heißt, es wächst asymptotisch streng langsamer.
Chepper
16
Beachten Sie, dass dies nichts mit der Komplexitätstheorie zu tun hat, sondern "nur" mit Aymptotik. Auch diese Art von Fragen ist in der Informatik wahrscheinlich besser gestellt .
Raphael

Antworten:

231

Sie müssen zur formalen Definition des großen O ( O) gehen, um diese Frage zu beantworten.

Die Definition ist, dass genau dann zu f(x)gehört, O(g(x))wenn die Grenze existiert, dh nicht unendlich ist. Kurz gesagt bedeutet dies, dass es eine Konstante gibt , so dass der Wert von niemals größer als ist .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

Im Falle Ihrer Frage lassen und lassen . Dann wird das noch unendlich wachsen. Daher gehört nicht dazu .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
quelle
5
Eine etwas leichter zu lesende Definition finden Sie hier
Alden,
3
Formal kann man die Grenze nicht überschreiten O(f(x)/g(x)); Die Big-O-Benachrichtigung ist eine Abkürzung für eine Reihe von Funktionen, nicht für eine einzelne Funktion, deren Wert Sie einschränken können. Ich denke jedoch, dass es wahr ist, dass Sie das zeigen können, f(x) = O(g(x))wenn es lim(x->infinity) f(x)/g(x)existiert.
Chepper
44
Das Limit muss nicht existieren; Das Verhältnis muss oben nur durch eine Konstante für ausreichend großes x begrenzt werden. Zum Beispiel ist 2 + sin (x) in O (1), aber (2 + sin (x)) / 1 nähert sich nicht einer Grenze als x-> unendlich.
Benutzer2357112 unterstützt Monica
2
Die Definition wäre korrekt mit lim supstatt lim.
David Eisenstat
11
@IvayloStrandjev Bitte beachten Sie, dass Ihre kurze Beschreibung falsch ist. Dies muss für einen ausreichend großen gelten x, nicht für alle Werte von x.
K.Steff
85

Ein schneller Weg, um zu sehen, dass n⋅2ⁿgrößer ist, besteht darin, eine Änderung der Variablen vorzunehmen. Lass m = 2ⁿ. Dann n⋅2ⁿ = ( log₂m )⋅m(nehmen Sie den Basis-2-Logarithmus auf beiden Seiten von m = 2ⁿgibt n = log₂m), und Sie können leicht zeigen, dass m log₂mschneller wächst als m.

chepner
quelle
3
Danke dir! Dies ist meiner Meinung nach die beste Antwort. Beweise, die auf formalen Definitionen basieren, sind korrekt, aber wenn Sie einen Stolperstein überwinden müssen, erledigt eine sehr komfortable und vertraute Analogie die Arbeit am besten und am schnellsten.
John P
1
Dumme Frage, was ist das lg? Logarithmus in Basis 2?
Pierre Arlaud
3
Es ist eine faule Abkürzung. In der Informatik bedeutet dies tendenziell Basis 2, da es hauptsächlich aus Divide-and-Conquer-Strategien resultiert. In der Big-O-Notation könnte es alles darstellen, da sich der Basis-x-Logarithmus einer Zahl von ihrem Basis-y-Logarithmus nur um einen konstanten Faktor unterscheidet, unabhängig von x und y.
Chepner
3
Ich sollte im Nachhinein beachten, dass dies lgdie ISO-Notation für einen Basis-10-Logarithmus ist und nicht die basenunabhängige Verwendung, die am häufigsten bei der Erörterung asymptotischer Laufzeiten verwendet wird. Siehe en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Okay, sicher, aber ich verstehe nicht, warum es offensichtlicher ist, dass m log m schneller wächst als m, als dass n 2 ^ n schneller wächst als 2 ^ n.
Djechlin
10

Ich bin damit einverstanden, dass dies n⋅2ⁿnicht der O(2ⁿ)Fall ist , aber ich dachte, es sollte expliziter sein, da das Limit der überlegenen Nutzung nicht immer gilt.

Nach der formalen Definition von Big-O: f(n)ist in, O(g(n))wenn es Konstanten gibt c > 0und n₀ ≥ 0solche, die für alles, was n ≥ n₀wir haben f(n) ≤ c⋅g(n). Es kann leicht gezeigt werden, dass für f(n) = n⋅2ⁿund keine solchen Konstanten existieren g(n) = 2ⁿ. Es kann jedoch gezeigt werden, dass g(n)in O(f(n)).

Mit anderen Worten, n⋅2ⁿist niedriger begrenzt durch 2ⁿ. Das ist intuitiv. Obwohl sie beide exponentiell sind und daher unter den meisten praktischen Umständen gleichermaßen unwahrscheinlich sind, können wir nicht sagen, dass sie in derselben Größenordnung liegen, da sie 2ⁿnotwendigerweise langsamer wachsen als n⋅2ⁿ.

zpr
quelle
f(n) = 2*2^nIch denke du meintest n*2^n?
tobias_k
4

Ich argumentiere nicht mit anderen Antworten, die besagen, dass das n⋅2ⁿschneller wächst als 2ⁿ. Aber das n⋅2ⁿWachstum ist immer noch nur exponentiell.

Wenn wir über Algorithmen sprechen, sagen wir oft, dass die zunehmende Komplexität exponentiell ist. So sehen wir sein 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, oder unsere n⋅2ⁿzu derselben Gruppe von Komplexität mit exponentiell wächst.

Um es ein bisschen mathematisch zu verstehen, betrachten wir eine Funktion f(x), die exponentiell wächst (nicht schneller als), wenn eine solche Konstante existiert c > 1, dass .f(x) = O(cx)

Für n⋅2ⁿdie Konstante ckann eine beliebige Zahl größer als 2, nehmen wir 3. Dann:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿund das ist weniger als 1für jeden n.

So 2ⁿwächst langsamer als n⋅2ⁿder letzte wiederum wächst langsamer als 2.000001ⁿ. Aber alle drei wachsen exponentiell.

Andrey
quelle
Im letzten Beispiel ist n * 2 ^ n größer als 2,000001 ^ n bis zu n = 34.726.000. Zu diesem Zeitpunkt ist 2 ^ n eine Zahl mit mehr als 10 Millionen Ziffern, also spielt es keine Rolle ...
gnasher729
1
@ gnasher729 Es ist nur eine Konstante, die wir weglassen können, da f (n) und c * f (n) hinsichtlich Big-O dieselbe Komplexität aufweisen. zB 40'000'000 * 2.000001 ^ n ist sofort größer als n * 2 ^ n. Aber Sie haben Recht, es spielt keine Rolle, ich würde sagen, es spielt keine Rolle, wenn wir exponentielle Wachstumsraten erreichen (es sei denn, wir erhalten nur kleine Werte von n).
Andrey
2

Sie fragten: "Ist die zweite in der gleichen Reihenfolge wie die erste? Ist die zusätzliche n-Multiplikation dort von Bedeutung?" Dies sind zwei verschiedene Fragen mit zwei verschiedenen Antworten.

n 2 ^ n wächst asymptotisch schneller als 2 ^ n. Das ist die beantwortete Frage.

Aber Sie könnten fragen: "Wenn Algorithmus A 2 ^ n Nanosekunden und Algorithmus B n 2 ^ n Nanosekunden benötigt, was ist das größte n, in dem ich eine Lösung in einer Sekunde / Minute / Stunde / Tag / Monat / Jahr finden kann? Und Die Antworten sind n = 29/35/41/46/51/54 vs. 25/30/36/40/45/49. Kein großer Unterschied in der Praxis.

Die Größe des größten Problems, das in der Zeit T gelöst werden kann, ist in beiden Fällen O (in T).

gnasher729
quelle