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