Что означает ?

15

Что означает ?logO(1)n

Я знаю нотацию big-O, но эта нотация для меня не имеет смысла. Я тоже ничего не могу найти по этому поводу, потому что поисковая система не может правильно это интерпретировать.

Для некоторого контекста предложение, в котором я нашел это, гласит: «[...] мы вызываем функцию [эффективную], если она использует пространство и самое большее время за единицу."log O ( 1 ) nO(logn)logO(1)n

Oebele
источник
1
Я согласен с тем, что не следует писать такие вещи, если только вы не очень четко понимаете, что это значит (и рассказывает читателю, что это такое) и не применяют те же правила последовательно.
Рафаэль
1
Да, вместо этого нужно написать это (log(n))O(1),
1
@RickyDemer Это не главное, что делает Рафаэль. означает точно ( log n ) b l a h . logblahn(logn)blah
Дэвид Ричерби
4
@Raphael Это стандартная запись в поле. Любой в курсе будет знать, что это значит.
Юваль Фильмус
1
@YuvalFilmus Я думаю, что множество противоречивых ответов является убедительным доказательством того, что ваше утверждение является ложным, и что действительно следует воздерживаться от использования таких обозначений.
Рафаэль

Ответы:

16

Вам нужно на мгновение игнорировать сильное чувство, что « » находится в неправильном месте, и продолжать с определением. е ( п ) = лог вывода ( 1 ) п означает , что существуют константы К и п 0 такое , что для всех п п 0 , ф ( п ) журнала K 1 п = войти K н .Of(n)=logO(1)nkn0nn0f(n)logk1n=logkn

Обратите внимание, что означает ( log n ) k . Функции вида log O ( 1 ) n часто называют полилогарифмическими, и вы можете услышать, как люди говорят: « f - это полилог  n ».logkn(logn)klogO(1)nfn

Вы заметите, что легко доказать, что , так как 2 n k n для всех n 0 , где k = 2 . Вам может быть интересно, если 2 log n = log O ( 1 ) n . Ответ да , поскольку при достаточно большой п , войти п 2 , поэтому 2 журнала п войти 2 п при достаточно большой 2n=O(n)2nknn0k=22logn=logO(1)nnlogn22lognlog2n .n

В соответствующей заметке вы часто будете видеть многочлены, записанные как : та же идея.nO(1)

Дэвид Ричерби
источник
Это не поддерживается общим соглашением о заполнителях.
Рафаэль
Я убираю свой комментарий: вы пишете во всех важных местах, чего достаточно.
Рафаэль
@ Рафаэль ОК. У меня еще не было времени проверить это, но я чувствовал, что вы, возможно, заказываете квантификаторы не так, как я. Я не уверен, что мы определяем один и тот же класс функций.
Дэвид Ричерби
Я думаю, что вы определяете my (2), а Том определяет . cR>0{logcn}
Рафаэль
9

Это злоупотребление нотацией, которое может быть понято общепринятым соглашением о заполнителях : всякий раз, когда вы найдете термин Ландау , замените его (на ваш взгляд или на бумаге) на произвольную функцию g O ( е ) .O(f)gO(f)

Так что если вы найдете

f(n)=logO(1)n

ты должен читать

для некоторого g O ( 1 ) .f(n)=logg(n)ngO(1).(1)

Обратите внимание на отличие от выражения « к степени некоторой константы»: g = n 1 / n - вполне вероятная возможность.logg=n1/n

Предупреждение: автор может использовать еще больше злоупотреблений примечаниями и хочет, чтобы вы читали

для некоторого g O ( 1 ) .е(N)О(журналграмм(N)N)граммО(1),(2)

Обратите внимание на разницу между (1) и (2); в то время как это работает, чтобы определить тот же самый набор положительных функций здесь, это не всегда работает. Не перемещайте в выражениях без заботы!О

Рафаэль
источник
3
Я думаю, что делает галочку то, что является монотонным и достаточно сюръективным для каждого фиксированного n . Monotonic делает положение O эквивалентным и дает вам (2) ⇒ (1); Чтобы пойти по другому пути, необходимо, чтобы g существовал, что может привести к сбою, если f ( n ) находится вне диапазона функции. Если вы хотите указать, что перемещение O опасно и не охватывает «дикие» функции, хорошо, но в данном конкретном случае это нормально для тех функций, которые представляют затраты. xlogx(n)nOgf(n)O
Жиль "ТАК - перестать быть злым"
@ Жиль Я ослабил утверждение до общего предупреждения.
Рафаэль
1
Этот ответ был сильно отредактирован, и теперь я в замешательстве: вы теперь утверждаете, что (1) и (2) фактически одинаковы?
Oebele
@Oebele Насколько я могу сказать, они не в целом, но здесь.
Рафаэль
Но что-то вроде не соответствует (1), но соответствует (2), верно? или я просто глупый сейчас? 3log2n
Oebele
6

Это означает, что функция увеличивается не более чем до степени некоторой константы, то есть log 2 ( n ) или log 5 ( n ) или log 99999 ( n ) ...loglog2(n)log5(n)log99999(n)

Том ван дер Занден
источник
Это может использоваться, когда известно, что рост функции ограничен некоторой постоянной степенью , но конкретная константа неизвестна или не указана. log
Ив Дауст
Это не поддерживается общим соглашением о заполнителях.
Рафаэль
2

«Максимум » означает, что существует постоянная c, такая, что измеряется O ( log c n ) .logO(1)ncO(logcn)

В более общем контексте эквивалентно утверждению, что существуют (возможно, отрицательные) константы a и b такие, что f ( n ) O ( log a n ) и f ( n ) Ω ( log b n ) .f(n)logO(1)nabf(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)nlogg(n)ng(n)O(1)O(g(n))h(n) , за исключением того, что вы получите результат, который не выражается так просто.O(g(n)h(n))


Поскольку детали нижней границы находятся, вероятно, на незнакомой территории, стоит взглянуть на некоторые контрпримеры. Напомним, что любой ограничен по величине ; что существует постоянная c такая, что для всех достаточно больших n , | г ( н ) | < с .g(n)O(1)cn|g(n)|<c

При рассмотрении асимптотического роста обычно имеет значение только верхняя граница , поскольку, например, вы уже знаете, что функция положительная. Однако в полной общности следует обратить внимание на нижнюю границу g ( n ) > - c .g(n)<cg(n)>c

Это означает, что, в отличие от более типичного использования обозначений big-oh, функции, которые слишком быстро уменьшаются, могут не попасть в ; например, 1logO(1)n потому что -logn

1n=log(logn)/(loglogn)nlogO(1)n
Показатель здесь возрастает по величине слишком быстро, чтобы быть ограниченнымO(1).
lognloglognO(1)
O(1)

Контрпример несколько иного рода состоит в том, что .1logO(1)n


источник
Разве я не могу просто взять и убрать заявленную нижнюю границу? b=0
Дэвид Ричерби
1
@DavidRicherby Нет, все еще говорит, что f ограничено снизу. Hurkyl: почему f ( n ) = 1 / n в журнале O ( 1 ) n ? b=0ff(n)=1/nlogO(1)n
Жиль "ТАК ... перестать быть злым"
@ Жиль: добавлено больше контента!
@ Жиль: ОК, конечно, он ограничен снизу цифрой 1. Что совсем не является границей для «большинства» применений нотации Ландау в CS.
Дэвид Ричерби
1) Ваше правило «двигаться вокруг » не всегда работает, и я не думаю, что «максимум» обычно имеет это значение; это просто избыточно. 2) Никогда O не подразумевает нижнюю границу. Вот когда вы используете Θ . 3) Если и как отрицательные функции обрабатываются данным определением O (даже без злоупотребления обозначениями), не всегда понятно. Большинство определений (при анализе алгоритмов) исключают их. Вы, кажется, принимаете определение, которое ограничивает абсолютное значение, что хорошо. OOΘO
Рафаэль