Всегда ли функции асимптотически сопоставимы?

15

Когда мы сравниваем сложность двух алгоритмов, обычно бывает, что либо либо (возможно, оба), где и время выполнения (например) двух алгоритмов.g ( n ) = O ( f ( n ) ) f gf(n)=O(g(n))g(n)=O(f(n))fg

Это всегда так? То есть всегда ли выполняется хотя бы одно из соотношений и , то есть для общих функций , ? Если нет, какие предположения мы должны сделать, и (почему) нормально, когда мы говорим о времени выполнения алгоритма?g ( n ) = O ( f ( n ) ) f gf(n)=O(g(n))g(n)=O(f(n))fg

Рафаэль
источник

Ответы:

21

Не каждая пара функций сравнима с обозначениями ; рассмотрим функции f ( n ) = n и g ( n ) = { 1, если  n  нечетно , n 2, если  n  четно . Более того, такие функции, как g ( n ) , действительно возникают как время выполнения алгоритмов. Рассмотрим очевидный алгоритм перебора, чтобы определить, является ли данное целое число n простым:O()f(n)=n

g(n)={1if n is odd, n2if n is even.
g(n)n
IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

Этот алгоритм требует арифметических операций, когда n чётно, O ( Θ(1)nоперации, когдаnсоставно, ноΘ(n)операции, когдаnпростое число. Таким образом, формально этот алгоритмнесопоставимс алгоритмом, использующимO(n)nΘ(n)n арифметических операций длякаждогоn.n n

В большинстве случаев, когда мы анализируем алгоритмы, нам нужна только асимптотическая верхняя граница вида для некоторой относительно простой функции f . Например, большинство учебников просто (и правильно) сообщает , что бежит в O ( N ) арифметические операции. Типичные функции верхней границы - это произведения экспонент, полиномов и логарифмов (хотя иногда встречаются и более экзотические звери, такие как факториалы и повторные логарифмы ). Нетрудно доказать, что любые две такие функции сравнимы.O(f(n))fIsPrime(n)O(n)

Смотрите также этот вопрос MathOverflow .

JeffE
источник
7

Из википедии определение большой буквы O:

xf(x)g(x)f(x)O(g(x))Mx0

|f(x)|<=M|g(x)|for allx>x0

Что происходит с функциями, которые не сходятся (к константе или бесконечности)?

f(x)=|xsin(x)|g(x)=10

x0x>x0x=kπf(x)=0MMf(x)>g(x)g(x)O(f(x))

|xsin(x)|Mx0x>x0f(x)<Mg(x)f(x)O(g(x))

Mf(x)g(x)g(x)=log(x)

Амит
источник
6

Вот пара монотонных функций, которые не асимптотически сопоставимы. Это актуально, потому что большинство сложностей, возникающих на практике, на самом деле монотонны.

f(x)=Γ(x+1)=x!
g(x)=Γ(x1/2+3/2)

Γ

Амброз Бижак
источник
4

Lexp(2logx+loglogx)/x2f,gLf=o(g)f=ω(g)f/g

В результате любые две «простые» функции, возникающие при анализе алгоритма , сравнимы. Здесь «простой» означает, что не существует определения по случаям (кроме конечного числа базовых случаев), и не появляются удивительные функции, такие как обратная функция Аккермана, которая иногда фигурирует во время выполнения.

Юваль Фильмус
источник
Ницца! Следует отметить, однако, что периодические элементы часто встречаются в анализе среднего случая (алгоритма D & C). Тот, кого я знаю, связан с обеих сторон константами, поэтому они не повредят асимптотической сопоставимости.
Рафаэль