Что означает ?
Я знаю нотацию big-O, но эта нотация для меня не имеет смысла. Я тоже ничего не могу найти по этому поводу, потому что поисковая система не может правильно это интерпретировать.
Для некоторого контекста предложение, в котором я нашел это, гласит: «[...] мы вызываем функцию [эффективную], если она использует пространство и самое большее время за единицу."log O ( 1 ) n
asymptotics
landau-notation
Oebele
источник
источник
Ответы:
Вам нужно на мгновение игнорировать сильное чувство, что « » находится в неправильном месте, и продолжать с определением. е ( п ) = лог вывода ( 1 ) п означает , что существуют константы К и п 0 такое , что для всех п ≥ п 0 , ф ( п ) ≤ журнала K ⋅ 1 п = войти K н .O f(n)=logO(1)n k n0 n≥n0 f(n)≤logk⋅1n=logkn
Обратите внимание, что означает ( log n ) k . Функции вида log O ( 1 ) n часто называют полилогарифмическими, и вы можете услышать, как люди говорят: « f - это полилог n ».logkn (logn)k журналO ( 1 )N е N
Вы заметите, что легко доказать, что , так как 2 n ≤ k n для всех n ≥ 0 , где k = 2 . Вам может быть интересно, если 2 log n = log O ( 1 ) n . Ответ да , поскольку при достаточно большой п , войти п ≥ 2 , поэтому 2 журнала п ≤ войти 2 п при достаточно большой2 n = O ( n ) 2 n ≤ k n n ≥ 0 к = 2 2 журналаn = logO ( 1 )N N журналn ≥ 2 2 журналаn≤log2n .n
В соответствующей заметке вы часто будете видеть многочлены, записанные как : та же идея.nO(1)
источник
Это злоупотребление нотацией, которое может быть понято общепринятым соглашением о заполнителях : всякий раз, когда вы найдете термин Ландау , замените его (на ваш взгляд или на бумаге) на произвольную функцию g ∈ O ( е ) .O(f) g∈O(f)
Так что если вы найдете
ты должен читать
для некоторого g ∈ O ( 1 ) .е( n ) = logграмм( н )N грамм∈ O ( 1 ) .( 1 )
Обратите внимание на отличие от выражения « к степени некоторой константы»: g = n ↦ 1 / n - вполне вероятная возможность.журнал грамм= n ↦ 1 / n
Предупреждение: автор может использовать еще больше злоупотреблений примечаниями и хочет, чтобы вы читали
для некоторого g ∈ O ( 1 ) .е( n ) ∈ O ( logграмм( н )н ) грамм∈ O ( 1 ) .( 2 )
Обратите внимание на разницу между (1) и (2); в то время как это работает, чтобы определить тот же самый набор положительных функций здесь, это не всегда работает. Не перемещайте в выражениях без заботы!О
источник
Это означает, что функция увеличивается не более чем до степени некоторой константы, то есть log 2 ( n ) или log 5 ( n ) или log 99999 ( n ) ...log log2(n) log5(n) log99999(n)
источник
«Максимум » означает, что существует постоянная c, такая, что измеряется O ( log c n ) .logO(1)n c O(logcn)
В более общем контексте эквивалентно утверждению, что существуют (возможно, отрицательные) константы a и b такие, что f ( n ) ∈ O ( log a n ) и f ( n ) ∈ Ω ( log b n ) .f(n)∈logO(1)n a b f(n)∈O(logan) f(n)∈Ω(logbn)
Легко пропустить нижнюю границу . В обстановке, где это будет иметь значение (что было бы весьма необычно, если вы заинтересованы исключительно в изучении асимптотического роста ), вы не должны иметь полной уверенности в том, что автор действительно имел в виду нижнюю границу, и вам придется полагаться на контекст, удостовериться.Ω(logbn)
Буквальный смысл записи выполняет арифметику с семейством функций, в результате чего получается семейство всех функций log g ( n ) n , где g ( n ) ∈ O ( 1 ) . Это работает почти так же, как умножение O ( g ( n ) ) на h ( n ) приводит к O ( g ( n ) h (logO(1)n logg(n)n g(n)∈O(1) O(g(n)) h(n) , за исключением того, что вы получите результат, который не выражается так просто.O(g(n)h(n))
Поскольку детали нижней границы находятся, вероятно, на незнакомой территории, стоит взглянуть на некоторые контрпримеры. Напомним, что любой ограничен по величине ; что существует постоянная c такая, что для всех достаточно больших n , | г ( н ) | < с .g(n)∈O(1) c n |g(n)|<c
При рассмотрении асимптотического роста обычно имеет значение только верхняя граница , поскольку, например, вы уже знаете, что функция положительная. Однако в полной общности следует обратить внимание на нижнюю границу g ( n ) > - c .g(n)<c g(n)>−c
Это означает, что, в отличие от более типичного использования обозначений big-oh, функции, которые слишком быстро уменьшаются, могут не попасть в ; например, 1logO(1)n
потому что
-logn
Контрпример несколько иного рода состоит в том, что .−1∉logO(1)n
источник