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

14

Rozumiem, że jest szybszy niż i wolniejszy niż . Trudno mi zrozumieć, jak faktycznie porównać i z gdzie . $\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.

asymptotics mathematical-analysis landau-notation

— Mihsathe
źródło

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.

7

Och kochanie, proszę nie!

— Raphael

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

$\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$

— 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

Ź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ć wzrost $n^f$ $\dfrac{n}{n^{1-f}}$ $n^{2/3}=n/n^{1/3}$

\frac{n}{\log n} vs. \frac{n}{n^{1 - f}} .

$\frac{n}{\log n} \quad \text{vs.} \quad \frac{n}{n^{1-f}}.$

Pamiętaj, że rośnie asymptotycznie wolniej niż jakikolwiek , dla każdego . $\log n$ $n^\varepsilon$ $\varepsilon>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

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: $f \prec g$

n^{α_{1}} (\log n)^{α_{2}} (\log \log n)^{α_{3}} ≺ n^{β_{1}} (\log n)^{β_{2}} (\log \log n)^{β_{3}} ⟺ (α_{1}, α_{2}, α_{3}) < (β_{1}, β_{2}, β_{3})

$n^{\alpha_1}(\log n)^{\alpha_2}(\log \log n)^{\alpha_3} \prec n^{\beta_1}(\log n)^{\beta_2}(\log \log n)^{\beta_3} \Longleftrightarrow (\alpha_1, \alpha_2, \alpha_3) < (\beta_1, \beta_2, \beta_3)$

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)$

(1 / 3, 0, 0) < (2 / 3, 0, 0) < (1, - 1, 0) \Rightarrow O (n^{1 / 3}) ≺ O (n^{2 / 3}) ≺ O (n / \log n)

$(1/3, 0, 0) < (2/3, 0, 0) < (1, -1, 0)\\ \Rightarrow \mathcal{O}(n^{1/3}) \prec \mathcal{O}(n^{2/3}) \prec \mathcal{O}(n/\log n)$

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