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

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 < $\Theta(n)$$\Theta(n\log n)$$\Theta(n/\log n)$$\Theta(n \log n)$$\Theta(n/\log n)$$\Theta(n^f)$$0 < f < 1$

Na przykład, jak zdecydować $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ lub $\Theta(n^{1/3})$

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

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

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

$\log n$ 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 .$2^n$$2^n$$n^k$$k$$\log n$$n^k$$k$

$n / \log n$ vs , ponieważ jest identyczne z: vs$n^k$$k < 1$$n / \log n$$n / n^{1-k}$

jako dla dużej , dla i dużej .$n^{1-k} > \log n$$n$$n / \log n > n^k$$k < 1$$n$

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

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

Pomyśl o jak o . Na przykład . Wtedy łatwo jest porównać wzrost$n^f$$\dfrac{n}{n^{1-f}}$$n^{2/3}=n/n^{1/3}$

Pamiętaj, że rośnie asymptotycznie wolniej niż jakikolwiek , dla każdego .$\log n$$n^\varepsilon$$\varepsilon>0$

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

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

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

Dotyczy twojego przykładu:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

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

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