n * log n oraz n / log n względem wielomianowego czasu działania

14

Rozumiem, że jest szybszy niż \ Theta (n \ log n) i wolniejszy niż \ Theta (n / \ log n) . Trudno mi zrozumieć, jak faktycznie porównać \ Theta (n \ log n) i \ Theta (n / \ log n) z \ Theta (n ^ f) gdzie 0 <f <1 .Θ ( n log n ) Θ ( n / log n ) Θ ( n log n ) Θ ( n / log n ) Θ ( n f ) 0 < f < 1Θ(n)Θ(nlogn)Θ(n/logn)Θ(nlogn)Θ(n/logn)Θ(nf)0<f<1

Na przykład, jak zdecydować Θ(n/logn) vs. Θ(n2/3) lub Θ(n1/3)

W takich przypadkach chciałbym uzyskać wskazówki dotyczące postępowania. Dziękuję Ci.

Mihsathe
źródło

Odpowiedzi:

3

Jeśli narysujesz kilka wykresów, będziesz w dobrej formie. Wolfram Alpha jest doskonałym źródłem informacji dla tego rodzaju dochodzeń:

równania

Wykres

Wygenerowane przez ten link . Zauważ, że na wykresie log (x) jest logarytmem naturalnym, dlatego równanie jednego wykresu wygląda trochę śmiesznie.


źródło
Poza tym, że zgadzam się z Raphaelem, to zdjęcie dałoby znacznie lepszy pomysł , wybór jeszcze większego zakresu pozwala zniknąć drugiej funkcji, co może być mylące.
phant0m
9

logn jest odwrotnością . Tak jak rośnie szybciej niż jakikolwiek wielomian niezależnie od tego, jak duże jest skończone , będzie rosło wolniej niż dowolne funkcje wielomianowe niezależnie od tego, jak małe jest niezerowe, dodatnie .2n2nnkklognnkk

n/logn vs , ponieważ jest identyczne z: vsnkk<1n/lognn/n1k

jako dla dużej , dla i dużej .n1k>lognnn/logn>nkk<1n

Taedrin
źródło
3

W przypadku wielu algorytmów czasami zdarza się, że stałe są różne, powodując, że jeden lub drugi jest szybszy lub wolniejszy dla mniejszych rozmiarów danych i nie jest tak uporządkowany według złożoności algorytmu.

To powiedziawszy, jeśli weźmiemy pod uwagę bardzo duże rozmiary danych, tj. który w końcu wygrywa, to O(n^f)jest szybszy niż O(n/log n)dla 0 < f < 1.

Duża część złożoności algorytmu polega na określeniu, który algorytm jest ostatecznie szybszy, dlatego często wystarczająca jest wiedza, że O(n^f)jest on szybszy niż O(n/log n)dla 0 < f < 1.

Ogólna zasada jest taka, że ​​mnożenie (lub dzielenie) przez log nbędzie ostatecznie nieistotne w porównaniu do mnożenia (lub dzielenie) przez n^fdowolne f > 0.

Aby to wyraźniej pokazać, zastanówmy się, co się stanie, gdy n wzrośnie.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Zauważ, że spada szybciej? To jest n^fkolumna.

Nawet jeśli fbył bliższy 1, n^fkolumna zacznie się po prostu wolniej, ale gdy n podwaja się, szybkość zmiany mianownika przyspiesza, podczas gdy mianownik n/log nkolumny wydaje się zmieniać ze stałą szybkością.

Narysujmy konkretny przypadek na wykresie

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Źródło: Wolfram Alpha

Wybrałem O(n^k)taki, który kjest dość bliski 1 (at 0.9). Wybrałem również stałe, aby początkowo były O(n^k)wolniejsze. Zauważ jednak, że ostatecznie „wygrywa” i zajmuje mniej czasu niż O(n/log n).

ronalchn
źródło
co z n / log n
To była trochę literówka, o to mi chodziło na początku. W każdym razie dodałem bardziej odpowiedni wykres, który pokazuje, że n^kostatecznie będzie szybszy, nawet jeśli wybrane zostaną stałe, tak że początkowo będzie on wolniejszy.
3

Pomyśl o jak o . Na przykład . Wtedy łatwo jest porównać wzrostnfnn1fn2/3=n/n1/3

nlognvs.nn1f.

Pamiętaj, że rośnie asymptotycznie wolniej niż jakikolwiek , dla każdego .lognnεε>0

A.Schulz
źródło
1

Porównując czasy działania, zawsze pomocne jest porównanie ich przy użyciu dużych wartości n. Dla mnie pomaga to budować intuicję, która funkcja jest wolniejsza

W twoim przypadku pomyśl o n = 10 ^ 10 i a = .5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Dlatego O (n ^ a) jest szybsze niż O (n / logn), kiedy 0 <a <1 Użyłem tylko jednej wartości, jednak możesz użyć wielu wartości, aby zbudować intuicję na temat funkcji


źródło
1
Nie pisz O(10^9), ale główna kwestia próbowania liczb w celu zbudowania intuicji jest słuszna.
Zawieść. To nie jest poprawne. Podstawiłeś jedną stałą n, która może być stronnicza. Gdybym wybrał inne stałe, mógłbym poprawić dowolny algorytm. Notacja Big O służy do ustalania trendów w tym, co będzie szybsze w dłuższej perspektywie. Aby to zrobić, musisz być w stanie wykazać, że jest szybszy dla dużych n, nawet jeśli jest wolniejszy, gdy n jest mniejszy.
Dzięki. Dodano wiele wartości i uwzględniono większe liczby
Należy zauważyć, że tylko dlatego, że f (a)> g (a) dla pewnej stałej a, niekoniecznie oznacza, że ​​O (f (x))> O (g (x)). Jest to przydatne do budowania intuicji, ale nie wystarcza do sformułowania rygorystycznego dowodu. Aby pokazać, że ta relacja się utrzymuje, musisz pokazać, że jest to prawdą dla WSZYSTKICH dużych n, a nie tylko jednego dużego n. Podobnie, musisz wykazać, że jest to prawdą dla wszystkich wielomianów stopnia dodatniego <1.
1

Niech oznacza „f rośnie asymptotycznie wolniej niż g”, to możesz zastosować następującą łatwą regułę dla polilogarytmiki? Funkcje:fg

nα1(logn)α2(loglogn)α3nβ1(logn)β2(loglogn)β3(α1,α2,α3)<(β1,β2,β3)

Relacja porządku między krotkami jest leksykograficzna. Tj. i(2,10)<(3,5)(2,10)>(2,5)

Dotyczy twojego przykładu:

O(n/logn)(1,1,0)

O(n2/3)(2/3,0,0)

O(n1/3)(1/3,0,0)

(1/3,0,0)<(2/3,0,0)<(1,1,0)O(n1/3)O(n2/3)O(n/logn)

Można powiedzieć: moc n dominuje moc log, która dominuje moc log log.

Źródło: Concrete Mathematics, str. 441

phant0m
źródło