Что означает тильда в нотации big-O?

Я читаю статью, и в своем описании сложности времени говорится, что сложность времени равна . $\tilde{O}(2^{2n})$

Я искал в интернете и википедии, но я не могу найти, что означает эта тильда в нотации big-O / Landau. В самой газете я также не нашел никаких подсказок по этому поводу. Что означает ? $\tilde{O}(\cdot)$

landau-notation Йоханнес Шауб - Литб
источник

"Я искал в интернете" Как?!? :-) Обычно на подобные вопросы моя первая реакция заключается в том, что Google сразу же ответит вам. Но для этого я понятия не имею, какой поисковый запрос я бы использовал!

Дэвид Ричерби

Я искал "символы тильды ландау", но ничего неясного не появилось. Я полагаю, что Google нужен некоторый ИИ, который знает, как выглядит тильда, и ищет его в визуализированных фотографиях TeX: p

Йоханнес Шауб - litb

Еще одна, которую ты иногда видишь, это Большая О звезда, то есть . Он обычно используется, например, с алгоритмами точного экспоненциального времени, и нотация подавляет факторы, полиномиально ограниченные во входном размере.

O^{*}

$O^*$

Юхо

Это вариант big-O, который «игнорирует» логарифмические факторы:

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

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

эквивалентно:

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

Из Википедии :

По сути, это big- нотации, игнорируя логарифмические факторы , поскольку последствия роста курса некоторых других супер-логарифмические функции указывают на взрыв роста скорости для больших размеров входных параметров , что является более важным для прогнозирования плохой производительности во время выполнения , чем точечные эффекты, обусловленные логарифмическим фактором (факторами) роста. Это обозначение часто используется, чтобы устранить «придирки» в пределах темпов роста, которые определены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку всегда равен для любой константы и любого ). $O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

Manlio
источник

Прав ли я, заключив, что и различны? Это сбивает с толку, потому что они, кажется, используются взаимозаменяемо.

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

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

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

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

Йоханнес Шауб -

@ JohannesSchaub-litb Да, есть функции, которые растут больше чем для каждого и все же растут меньше, чем , и, следовательно, включаются в первое, но не во второе. В любом случае: смысл этой записи в том, чтобы показать только важную часть асимптотической сложности, и обычно не считается важным.

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

Бакуриу

Как следствие, совпадает с . @ JohannesSchaub-litb совпадает с . В случае, если вы действительно имели в виду , это включает в себя , но также некоторые функции растут немного быстрее. Люди часто используют его вместо потому что это не так, - менее известное обозначение, и потеря точности часто не имеет значения.

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

Эмиль Йержабек

Ах, теперь я понимаю, спасибо. Это имеет большой смысл

Йоханнес Шауб - Lit

Что означает тильда в нотации big-O?

Ответы: