Czy 2 ^ ni 2 * n są w tej samej złożoności czasowej?

178

Zasoby, które znalazłem na temat złożoności czasowej, nie są jasne, kiedy można zignorować terminy w równaniu złożoności czasowej, w szczególności na przykładach innych niż wielomianowe.

Jest dla mnie jasne, że biorąc pod uwagę coś w formie n 2 + n + 1, ostatnie dwa terminy są nieistotne.

W szczególności, biorąc pod uwagę dwie kategorie, 2 n i n * (2 n ), czy druga jest w tej samej kolejności co pierwsza? Czy dodatkowe mnożenie tam ma znaczenie? Zwykle zasoby po prostu mówią, że x n ma charakter wykładniczy i rośnie znacznie szybciej ... a następnie iść dalej.

Rozumiem, dlaczego tak się nie stanie, ponieważ 2 n znacznie przewyższy n, ale ponieważ nie są one sumowane razem, będzie to miało duże znaczenie przy porównywaniu dwóch równań, w rzeczywistości różnica między nimi zawsze będzie czynnikiem n, co wydaje się co najmniej ważne.

algorithm big-o complexity-theory time-complexity matty-d
źródło
8
Moim zdaniem, biorąc pod uwagę, że NLogN jest uważany za wolniejszy niż N, ale większości ludzi tak naprawdę nie obchodzi, o ile, można bezpiecznie powiedzieć, że N2 ^ N jest po prostu wolniejszy niż 2 ^ N, ale nie jest „wystarczająco wolny” dla ludzi dbać ..
Jack
@ Tobias_k, rozumiem ten punkt, ale rozważmy przykład O (n!). Czy dodatkowy termin n naprawdę byłby inny? O (n!) Oznacza O (n * n!), Ponieważ O (n!) Oznacza O ((n + 1)!) Aka ten sam wykres po prostu przesunięty. Wzrost jest jednak taki sam ... W tym przypadku, chociaż wzrost jest ściśle duży, czy wzrost jest inny? czy nie na tym zależy złożoność?
matty-d
3
@JackWu, ale większości ludzi tak naprawdę nie obchodzi, o ile trzeba posortować setki milionów rekordów za pomocą nlogn zamiast n :)
CB
4
W rzeczywistości n! = o((n+1)!)rośnie asymptotycznie ściśle wolniej.
chepner
16
Zauważ, że nie ma to nic wspólnego z teorią złożoności, chodzi tylko o aymptotyki. Ponadto tego rodzaju pytania są prawdopodobnie lepsze w przypadku informatyki .
Raphael

Odpowiedzi:

231

Będziesz musiał przejść do formalnej definicji dużej litery O ( O), aby odpowiedzieć na to pytanie.

Definicja ta f(x)należy do O(g(x))wtedy i tylko wtedy, gdy limit istnieje, tzn. Nie jest nieskończonością. W skrócie oznacza to, że istnieje stała , taka, że ​​wartość nigdy nie jest większa niż .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

W przypadku twojego pytania pozwól i pozwól . Zatem jest to, co wciąż będzie rosło nieskończenie. Dlatego nie należy do .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
źródło
5
Nieco łatwiejszą do odczytania definicję można znaleźć tutaj
Alden
3
Formalnie rzecz biorąc, nie możesz przekroczyć granicy O(f(x)/g(x)); powiadomienie big-O jest skrótem dla zestawu funkcji, a nie pojedynczej funkcji, której wartość można ograniczyć. Myślę jednak, że to prawda, że ​​możesz pokazać, że f(x) = O(g(x))jeśli lim(x->infinity) f(x)/g(x)istnieje.
chepner
44
Limit nie musi istnieć; stosunek musi być ograniczony wyłącznie stałą dla wystarczająco dużego x. Na przykład 2 + sin (x) jest w O (1), ale (2 + sin (x)) / 1 nie zbliża się do granicy jako x-> nieskończoność.
user2357112 obsługuje Monikę
2
Definicja byłaby poprawna z lim supzamiast lim.
David Eisenstat
11
@IvayloStrandjev pamiętaj, że krótki opis jest niepoprawny. Musi to być prawdą w przypadku wystarczająco dużych wartości x, a nie wszystkich wartości x.
K.Steff
85

Szybkim sposobem, aby przekonać się, że n⋅2ⁿjest większy, jest zmiana zmiennej. Let m = 2ⁿ. Następnie n⋅2ⁿ = ( log₂m )⋅m(biorąc logarytm podstawy 2 po obu stronach m = 2ⁿpodarunków n = log₂m), możesz łatwo pokazać, że m log₂mrośnie szybciej niż m.

chepner
źródło
3
Dziękuję Ci! To jest najlepsza odpowiedź moim zdaniem. Dowody oparte na formalnych definicjach są poprawne, ale jeśli masz jakiś przeszkodę do pokonania, bardzo wygodna i znajoma analogia wykona zadanie najlepiej i najszybciej.
John P
1
Głupie pytanie, co to jest lg? Logarytm w bazie 2?
Pierre Arlaud
3
To leniwy skrót. W informatyce zwykle oznacza bazę 2, ponieważ wynika głównie ze strategii dziel i zwyciężaj. W notacji Big-O może reprezentować wszystko, ponieważ logarytm bazowy x liczby różni się od logarytmu bazowego y tylko stałym współczynnikiem, niezależnie od xiy.
chepner
3
Z perspektywy czasu powinienem zauważyć, że lgjest to notacja ISO dla logarytmu base-10, a nie użycie agnostyczne bazowe najczęściej używane podczas omawiania asymptotycznych czasów pracy. Zobacz en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Okej, jasne, ale nie rozumiem, dlaczego bardziej oczywiste jest, że m log m rośnie szybciej niż m, niż że n 2 ^ n rośnie szybciej niż 2 ^ n.
djechlin
10

Zgadzam się, że tego n⋅2ⁿnie ma O(2ⁿ), ale pomyślałem, że powinno to być bardziej wyraźne, ponieważ maksymalne użycie limitu nie zawsze obowiązuje.

Według formalnej definicji Big-O: f(n)jest, O(g(n))jeśli istnieją stałe c > 0i n₀ ≥ 0takie, które n ≥ n₀mamy dla wszystkich f(n) ≤ c⋅g(n). Można łatwo wykazać, że nie istnieją takie stałe dla f(n) = n⋅2ⁿi g(n) = 2ⁿ. Można jednak pokazać, że g(n)jest w O(f(n)).

Innymi słowy, n⋅2ⁿjest ograniczony przez 2ⁿ. To jest intuicyjne. Chociaż oba są wykładnicze, a zatem jest mało prawdopodobne, aby były stosowane w najbardziej praktycznych okolicznościach, nie możemy powiedzieć, że są tego samego rzędu, ponieważ z 2ⁿkonieczności rośnie wolniej niż n⋅2ⁿ.

zpr
źródło
f(n) = 2*2^nMyślę, że miałeś na myśli n*2^n?
tobias_k
4

Nie kłócę się z innymi odpowiedziami, które mówią, że n⋅2ⁿrośnie szybciej niż 2ⁿ. Ale n⋅2ⁿwzrost jest wciąż tylko wykładniczy.

Kiedy mówimy o algorytmach, często mówimy, że złożoność czasu rośnie wykładniczo. Tak, uważamy za 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, lub naszych n⋅2ⁿbyć sama grupa złożoności z wykładniczy rośnie.

Aby nadać temu nieco matematyczny sens, uważamy, że funkcja f(x)rośnie (nie szybciej niż) wykładniczo, jeśli istnieje taka stała c > 1, że .f(x) = O(cx)

Ponieważ n⋅2ⁿstała cmoże być dowolną liczbą większą niż 2, weźmy 3. Następnie:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿa to mniej niż 1jakikolwiek n.

Więc 2ⁿrośnie wolniej niż n⋅2ⁿ, a ostatni z kolei rośnie wolniej niż 2.000001ⁿ. Ale wszystkie trzy rosną wykładniczo.

Andrey
źródło
W ostatnim przykładzie n * 2 ^ n jest większe niż 2,000001 ^ n do n = 34 726 000. W tym momencie 2 ^ n to liczba z ponad 10 milionami cyfr, więc to naprawdę nie ma znaczenia ...
gnasher729,
1
@ gnasher729 To tylko stała, którą możemy pominąć, ponieważ f (n) i c * f (n) ma tę samą złożoność pod względem dużego-O. np. 40'000'000 * 2.000001 ^ n jest od razu większe niż n * 2 ^ n. Ale masz rację, to tak naprawdę nie ma znaczenia, powiedziałbym, że to tak naprawdę nie ma znaczenia, gdy osiągniemy wykładniczy wzrost (chyba że otrzymamy tylko małe wartości n).
Andrey
2

Zapytałeś: „czy druga jest w tej samej kolejności co pierwsza? Czy dodatkowe mnożenie n ma znaczenie?” To są dwa różne pytania z dwiema różnymi odpowiedziami.

n 2 ^ n rośnie asymptotycznie szybciej niż 2 ^ n. Na to pytanie odpowiedziano.

Ale możesz zapytać "jeśli algorytm A zajmuje 2 ^ n nanosekund, a algorytm B zajmuje 2 ^ n nanosekund, co jest największym n, gdzie mogę znaleźć rozwiązanie w sekundę / minutę / godzinę / dzień / miesiąc / rok? I odpowiedzi to n = 29/35/41/46/51/54 vs. 25/30/36/40/45/49 Nie ma dużej różnicy w praktyce.

Rozmiar największego problemu, jaki można rozwiązać w czasie T, wynosi w obu przypadkach O (1n T).

gnasher729
źródło