Sortowanie funkcji według asymptotycznego wzrostu

Załóżmy, że mam na przykład listę funkcji

$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$

Jak sortować je asymptotycznie, tj. Według relacji zdefiniowanej przez

$\qquad f \leq_O g \iff f \in O(g)$ ,

zakładając, że rzeczywiście są one porównywalne parami (patrz także tutaj )? Używanie definicji $O$ wydaje się niewygodne i często trudno jest udowodnić istnienie odpowiednich stałych $c$ i $n_0$ .

Chodzi o miary złożoności, dlatego interesuje nas zachowanie asymptotyczne, ponieważ $n \to +\infty$ , i zakładamy, że wszystkie funkcje przyjmują tylko wartości nieujemne ( $\forall n, f(n) \ge 0$ ).

Jeśli potrzebujesz ścisłego dowodu, często przydatny jest następujący lemat. bardziej przydatne niż definicje.

Jeśli $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ istnieje zatem

• $c=0 \qquad \ \,\iff f \in o(g)$ ,
• i$c \in (0,\infty) \iff f \in \Theta(g)$
• .$c=\infty \quad \ \ \ \iff f \in \omega(g)$

Dzięki temu powinieneś być w stanie zamówić większość funkcji pojawiających się w analizie algorytmów¹. Jako ćwiczenie udowodnij to!

Oczywiście musisz być w stanie odpowiednio obliczyć limity. Oto kilka przydatnych sztuczek pozwalających rozbić skomplikowane funkcje na podstawowe:

• Wyraź obie funkcje jako i porównaj wykładniki; jeśli ich stosunek ma tendencję do 0 lub ∞ , to samo dzieje się z ilorazem pierwotnym.$e^{\dots}$$0$$\infty$

• Mówiąc bardziej ogólnie: jeśli masz wypukłą, ciągle różnicowalną i ściśle zwiększającą się funkcję , abyś mógł ponownie zapisać swój iloraz jako$h$

  ,$\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$

  za pomocą i$g^* \in \Omega(1)$

  ,$\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$

  następnie

  .$\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

  ^{Zobacz tutaj dokładny dowód tej reguły (w języku niemieckim).}

• Zastanów się nad kontynuacją swoich funkcji nad rzeczywistością. Możesz teraz użyć reguły L'Hôpital ; uważaj na jego warunki²!

• Zobacz dyskretny odpowiednik Stolz – Cesàro .

• Kiedy wyskakują silnie, użyj wzoru Stirlinga :

  $\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

Przydatne jest również utrzymanie puli podstawowych relacji, które udowodnisz raz i których często używasz, takich jak:

• logarytmy rosną wolniej niż wielomiany, tj

  dla wszystkich α , β > 0 .$\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$$\alpha, \beta > 0$

• kolejność wielomianów:

  dla wszystkichα<β.$\qquad\displaystyle n^\alpha \in o(n^\beta)$$\alpha < \beta$

• wielomiany rosną wolniej niż wykładnicze:

  dla wszystkichαic>1.$\qquad\displaystyle n^\alpha \in o(c^n)$$\alpha$$c > 1$

---

Może się zdarzyć, że powyższy lemat nie ma zastosowania, ponieważ limit nie istnieje (np. Gdy funkcje oscylują). W takim przypadku weź pod uwagę następującą charakterystykę klas Landaua, stosując limonki lepsze / gorsze :

Z mamy$c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$

• i$0 \leq c_s < \infty \iff f \in O(g)$
• .$c_s = 0 \iff f \in o(g)$

Za pomocą mamy$c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$

• i$0 < c_i \leq \infty \iff f \in \Omega(g)$
• .$c_i = \infty \iff f \in \omega(g)$

Ponadto,

• i$0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$
• .$c_i = c_s = 1 \iff f \sim g$

---

Sprawdź tu i tutaj, jeśli moja notacja mnie myli.

---

¹ Nota bene: Mój kolega napisał funkcję Mathematica, która robi to z powodzeniem dla wielu funkcji, więc lemat naprawdę redukuje zadanie do obliczeń mechanicznych.

² Zobacz także tutaj .

Kolejna wskazówka: czasami zastosowanie funkcji monotonicznej (takiej jak log lub exp) do funkcji sprawia, że ​​wszystko jest wyraźniejsze.

Skiena przedstawia posortowaną listę relacji dominacji między najczęstszymi funkcjami w swojej książce, The Algorytm Design Manual:

$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$\gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$

Tutaj $\alpha(n)$ oznacza odwrotną funkcję Ackermanna .

Wskazówka: narysuj wykresy tych funkcji za pomocą czegoś takiego jak Wolfram Alpha, aby poczuć, jak się rozwijają. Zauważ, że nie jest to zbyt precyzyjne, ale jeśli spróbujesz tego dla wystarczająco dużych liczb, powinieneś zobaczyć porównawcze wzorce wzrostu. To oczywiście nie zastąpi dowodu.

Np. Spróbuj: dziennik wydruku (log (n)) od 1 do 10000, aby zobaczyć pojedynczy wykres lub dziennik wydruku (log (n)) i dziennik wydruku (n) od 1 do 10000, aby zobaczyć porównanie.

Proponuję postępować zgodnie z definicjami różnych zapisów. Rozpocznij od dowolnej pary wyrażeń i określ ich kolejność, jak opisano poniżej. Następnie dla każdego dodatkowego elementu znajdź jego pozycję na posortowanej liście za pomocą wyszukiwania binarnego i porównania, jak poniżej. Na przykład posortujmy i 2 n , pierwsze dwie funkcje n, aby rozpocząć listę.$n^{\log\log n}$$2^n$

$n = 2^{\log n}$$n^{\log\log n} = (2^{\log n})^{\log\log n} = 2^{\log n\log\log n}$$n^{\log\log n} = 2^{\log n\log\log n} \in o(2^n)$$c > 0$$n_0$$n \geq n_0$$c(n^{\log\log n}) = c(2^{\log n\log\log n}) < 2^n$

$3^n$$2^n$$3^n = (2^{\log 3})^n = 2^{n\log3}$$2^n \in o(3^n) = o(2^{n \log 3})$

Itp.

Oto lista z Wikipedii , im niższa w tabeli, tym większa klasa złożoności;

$$\begin{array}{|l|l|} \hline Name & \text{Running Time} \\ \hline \text{Constant time} & \mathcal{O}(1) \\ \text{Inverse Ackermann time} & \mathcal{O}(a(n)) \\ \text{Iterated logarithmic time} & \mathcal{O}(\log^*n) \\ \text{Log-logarithmic} & \mathcal{O}(n \log n) \\ \text{Logarithmic time} & \mathcal{O}(\log n) \\ \text{Polylogarithmic time} & poly(\log n) \\ \text{Fractional power} & \mathcal{O}(n^c) ,\text{where } 0<c<1 \\ \text{Linear time} & \mathcal{O}(n) \\ \text{"n log star n" time} & \mathcal{O}(n \log^* n) \\ \text{Quasilinear time} & \mathcal{O}(n \log n) \\ \text{Quadratic time} & \mathcal{O}(n^2) \\ \text{Cubic time} & \mathcal{O}(n^3) \\ \text{Polynomial time} & poly(n) = 2^{\mathcal{O}(\log n)} \\ \text{Quasi-polynomial time} & 2^{\mathcal{O}(poly(\log n))} \\ \text{Sub-exponential time (first definition)} & \mathcal{O}(2^{n^{\epsilon}}), \epsilon >0 \\ \text{Sub-exponential time (second definition)} & 2^{\mathcal{o}(n)}\\ \text{Exponential time(with linear exponent)} & 2^{\mathcal{O}(n)} \\ \text{Exponential time} & 2^{poly(n)} \\ \text{Factorial time} & \mathcal{O}(n!) \\\hline \end{array}$$

Uwaga : $poly(x) = x^{\mathcal{O}(1)}$