Apa artinya tilde, dalam notasi O besar?

Saya membaca makalah, dan dikatakan dalam deskripsi kompleksitas waktunya bahwa kompleksitas waktu adalah . $\tilde{O}(2^{2n})$

Saya telah mencari di internet dan wikipedia, tetapi saya tidak dapat menemukan apa yang dilambangkan tilde ini dalam notasi O-Landau besar. Di koran itu sendiri saya juga tidak menemukan petunjuk tentang ini. Apa artinya? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
sumber

"Saya sudah mencari di internet" Bagaimana?!? :-) Biasanya, untuk pertanyaan seperti ini, reaksi pertama saya adalah bahwa Google akan segera memberi tahu Anda jawabannya. Tapi untuk yang ini, saya tidak tahu istilah pencarian apa yang akan saya gunakan!

David Richerby

Saya mencari "simbol landau tilde" tetapi tidak ada yang konklusif muncul. Saya kira google membutuhkan beberapa AI yang tahu bagaimana tilde terlihat secara visual dan mencarinya dalam gambar TeX yang diberikan: p

Johannes Schaub - litb

Satu lagi yang kadang-kadang Anda lihat adalah bintang Oh Besar, yaitu,

. Ini umum digunakan dengan eg, algoritma waktu eksponensial yang tepat, dan notasi menekan faktor-faktor yang secara polinomi terbatas pada ukuran input.

O^{*}

$O^*$

Juho

Jawaban:

Ini adalah varian dari big-O yang "mengabaikan" faktor logaritmik:

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

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

setara dengan:

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

Dari Wikipedia :

$O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

manlio
sumber

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

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

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

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

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

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

Ah saya mengerti sekarang, terima kasih. Ini sangat masuk akal

Johannes Schaub - litb