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

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

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

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

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

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

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

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

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

$x$$f(x)$$g(x)$$f(x) \in O(g(x))$$M$$x_0$

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

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

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

$x_0$$x > x0$$x = k\pi$$f(x) = 0$$M$$Mf(x) > g(x)$$g(x) \; \not\in O(f(x))$

$|xsin(x)|$$M$$x_0$$x > x_0$$f(x) < Mg(x)$$f(x) \not\in O(g(x))$

$Mf(x)$$g(x)$$g(x) = \log(x)$

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

$\Gamma$

$\mathcal{L}$$\exp(2\sqrt{\log x + \log\log x})/x^2$$f,g \in \mathcal{L}$$f = o(g)$$f = \omega(g)$$f/g$

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