Co oznacza tylda w notacji big-O?

Czytam artykuł i w jego opisie złożoności czasowej napisano, że złożoność czasowa to . $\tilde{O}(2^{2n})$

Przeszukałem internet i wikipedię, ale nie mogę znaleźć tego, co oznacza tylda w notacji big-O / Landau. W samym artykule nie znalazłem też żadnych wskazówek na ten temat. Co oznacza ? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
źródło

„Przeszukałem internet” Jak? :-) Zwykle w przypadku takich pytań moją pierwszą reakcją jest to, że Google natychmiast poda odpowiedź. Ale w tym przypadku nie mam pojęcia, jakiego wyszukiwanego terminu użyłbym!

David Richerby,

Szukałem „tylda symboli landau”, ale nie pojawiło się nic rozstrzygającego. Myślę, że Google potrzebuje sztucznej inteligencji, która wie, jak wygląda tylda i szuka tego w renderowanych zdjęciach TeX: p

Johannes Schaub - litb

Inną, którą czasem widzisz, jest gwiazda Big Oh, czyli . Jest powszechnie używany np. Z dokładnymi algorytmami czasu wykładniczego, a notacja tłumi czynniki ograniczone wielomianowo w wielkości wejściowej.

O^{*}

$O^*$

Juho

Jest to wariant dużego O, który „ignoruje” czynniki logarytmiczne:

f (n) \in \tilde{O} (h (n))

$f(n) \in \tilde O(h(n))$

jest równa:

\exists k : f (n) \in O (h (n) \log^{k} (h (n)))

$\exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right)$

Z Wikipedii :

Zasadniczo jest to notacja wielka- , ignorująca czynniki logarytmiczne, ponieważ efekty tempa wzrostu niektórych innych funkcji superlogarytmicznych wskazują na eksplozję tempa wzrostu dla dużych parametrów wejściowych, która jest ważniejsza dla przewidywania złej wydajności w czasie wykonywania niż efekty drobniejszych punktów wnoszone przez czynnik (czynniki) logarytmiczny. Notacja ta jest często używana w celu uniknięcia „szarpania” w ramach stóp wzrostu, które są określone jako zbyt ściśle ograniczone do rozpatrywanych spraw (ponieważ jest zawsze dla dowolnego stałego i dowolnego ). $O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

manlio
źródło

Czy mam rację, stwierdzając, że i są różne? Jest to mylące, ponieważ wydaje się, że są używane zamiennie.

O (2^{2 n} + o (n))

$O(2^{2n} + o(n))$

\tilde{O} (2^{2 n})

$\tilde{O}(2^{2n})$

Johannes Schaub - litb

@ JohannesSchaub-litb Tak, istnieją funkcje, które rosną więcej niż dla każdego a jednak rosną mniej niż , a zatem są uwzględnione w pierwszym, ale nie drugim. W każdym razie: celem tego zapisu jest pokazanie tylko ważnej części asymptotycznej złożoności i ogólnie nie jest uważane za ważne.

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

Bakuriu

W konsekwencji jest taka sama jak . @ JohannesSchaub-litb jest taki sam jak . Jeśli naprawdę miałeś na myśli , obejmuje to , ale także kilka funkcji rosnących nieco szybciej. Ludzie często używają go zamiast ponieważ nie jest to złe, to mniej znany zapis, a utrata precyzji często nie ma znaczenia.

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

O (2^{2 n} p o l y (n))

$O(2^{2n}\mathrm{poly}(n))$

O (2^{2 n} + o (n))

$O(2^{2n}+o(n))$

O (2^{2 n})

$O(2^{2n})$

O (2^{2 n + o (n)})

$O(2^{2n+o(n)})$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O}

$\tilde O$

Emil Jeřábek

Ach, rozumiem teraz, dzięki. To ma sens

Johannes Schaub - litb

Co oznacza tylda w notacji big-O?

Odpowiedzi: