Алгоритм может иметь отрицательный коэффициент в своей временной сложности, но в целом алгоритм будет иметь некоторую положительную временную сложность. В качестве примера из Википедии возьмите функцию f(x)=6x^4-2x^3+5. Они решают для сложности O(x^4) следующим образом:
для некоторого подходящего выбора x0 и M и для всех x> x0. Чтобы доказать это, пусть x0 = 1 и M = 13. Тогда для всех x> x0:
Итак,
То есть, даже если в исходном уравнении присутствуют отрицательные коэффициенты, все равно сохраняется некоторая положительная общая временная сложность, основанная на члене с наивысшим порядком мощности.
А как насчет нижних границ? По определению мы можем найти нижнюю границу любой функции, используя следующее определение : так как n идет в бесконечность, то для некоторой константы k и некоторого n0 мы имеем, что выполняется следующее для всех n>n0:
Давайте предположим, что вышеуказанная функция f (x) также является Omega (x ^ 4). Это означает, что:
6x ^ 4 - 2x ^ 3 + 5> = kx ^ 4
Решение для k:
k <= (6x ^ 4 - 2x ^ 3 + 5) / (x ^ 4) </p>
k <= 6 - 2x ^ -1 + 5x ^ -4 </p>
Термин (2 / x) приближается к 0, как и (5 / x ^ 4), поэтому мы можем выбрать k=2 для некоторого большого x0 = 30. Чтобы показать, что это верно, мы покажем, что:
6x ^ 4 - 2x ^ 3 + 5> = 2x ^ 4, где x> 30
4x ^ 4 - 2x ^ 3 + 5> = 0
Что верно. Итак, f(x) - это Омега (x ^ 4), и мы также можем заключить, что мы нашли такую жесткую границу, что f(x) - это Тета (x ^ 4).
Почему это работает, хотя коэффициент был отрицательным? И для обозначений Big O и Big Omega мы ищем границу, такую, что после некоторой точки одна функция доминирует над другой. То есть , как показывают эти графики :
http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOGraph.png - Большой O
http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOmegaGraph.png - Большая Омега
Думая о нашем первоначальном значении f (x), 6x^4 растет быстрее, чем 2x^4 (наша функция kg (x)). После некоторого пункта термин 6x^4 будет опережать рост 2x^4 таким образом, что он всегда больше 2x^4. Графически две функции выглядят так:
http://www3.wolframalpha.com/Calculate/MSP/MSP8991a0763a90cg9c64500002i49d6b33c5684hg?MSPStoreType=image/gif&s=47&w=319&h=132&cdf=RangeControl
Несмотря на отрицательный коэффициент, ясно, что kg(x) является нижней границей f(x).
Теперь, всегда ли это верно для любой полиномиальной функции с любым отрицательным коэффициентом - что функция f(x) с любыми коэффициентами будет связана своими полиномами наивысшей степени? Нет. Если член с наивысшей степенью имеет отрицательный коэффициент, то границы не совсем совпадают. Возьми f(x) = -2x^2. Мы можем показать, что f(x) = O(x^2):
-2x ^ 2 <= cx ^ 2
-2 <= с </p>
Что может быть удовлетворено любым c>0 (так как c по определению является положительной константой). Однако, если мы попытаемся сделать то же самое для нижней границы:
-2x ^ 2> = cx ^ 2
-2 <= с </p>
Тогда мы не можем найти правильное c, потому что снова c должно быть неотрицательным.