Асимптотическая оценка

Материал из Википедии — свободной энциклопедии

Для описания скорости роста функций используется О-символика. Например, когда мы говорим, что время выполнения $T(n)\,\!$ некоторой программы имеет порядок $O(n^2)\,\!$ (читается «о-большое от n в квадрате» или просто «о от n в квадрате»), то подразумевается, что существуют положительные константы $c\,\!$ и $n_0\,\!$ такие, что для всех $n\,\!$ , больших или равных $n_0\,\!$ выполняется неравенство $T(n)<cn^2\,\!$ .

[править] Примеры

Предположим, что $T(0)=1\,\!$ , $T(1)=4\,\!$ и в общем случае $T(n)=(n+1)^2\,\!$ . Тогда $T(n)\,\!$ имеет порядок $0^2\,\!$ : если положить $n_0=1\,\!$ и $c=4\,\!$ , то легко показать, что для $n\ge1\,\!$ будет выполняться неравенство $(n+1)^2<\;4n^2\,\!$ . Отметим, что нельзя положить $n_0=0\,\!$ , так как $T(0)=1\,\!$ и, следовательно, это значение при любой константе с больше $cO^2=0\,\!$ .

Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что $T(n)\,\!$ имеет порядок $O(f(n))\,\!$ , если существуют константы $c\,\!$ и $n_0\,\!$ такие, что для всех $n>n_0\,\!$ выполняется неравенство $T(n)\ge c*f(n)\,\!$ . Для программ, у которых время выполнения имеет порядок $O(f(n))\,\!$ , говорят, что они имеют «порядок» (или «степень») роста $f(n)\,\!$ .

Функция $T(n)=3n^3+2n^2\,\!$ имеет степень роста $O(n^3)\,\!$ . Чтобы это показать, надо положить $n_0=0\,\!$ и $c=5\,\!$ , так как легко видеть, что для всех целых $n>0\,\!$ выполняется неравенство $3n^3+2n^2\le5n^3\,\!$ . Можно, конечно, сказать, что $T(n)\,\!$ имеет порядок $O(n^4)\,\!$ , но это более слабое утверждение, чем то, что $T(n)\,\!$ имеет порядок роста $O(n^3)\,\!$ . В качестве следующего примера докажем, что функция $3^n\,\!$ не может иметь порядок $O(2^n)\,\!$ . Предположим, что существуют константы $c\,\!$ и $n_0\,\!$ такие, что для всех $n \ge n_0\,\!$ выполняется неравенство $3^n \ge c2^n\,\!$ . Тогда $c \ge {\left( \frac{3}{2} \right)}^n\,\!$ для всех $n \ge n_0\,\!$ . Но ${\left( \frac{3}{2} \right)}^n\,\!$ принимает любое, как угодно большое, значение при достаточно большом $n\,\!$ , поэтому не существует такой константы $c\,\!$ , которая могла бы мажорировать ${\left( \frac{3}{2} \right)}^n\,\!$ для всех $n\,\!$ .

Когда мы говорим, что $T(n)\,\!$ имеет степень роста $O(f(n))\,\!$ , то подразумевается, что $f(n)\,\!$ является верхней границей скорости роста $T(n)\,\!$ . Чтобы указать нижнюю границу скорости роста $T(n)\,\!$ , используется обозначение: $T(n)\,\!$ есть $\Omega(g(n))\,\!$ (читается «омега-большое от g(n)» или просто «омега от g(n)»), это подразумевает существование такой константы $c\,\!$ , что бесконечно часто (для бесконечного числа значений $n\,\!$ ) выполняется неравенство $T(n)>cg(n)\,\!$ .

Примечание: Отметим асимметрию в определениях $O\,\!$ и $\Omega\,\!$ -символики. Такая асимметрия бывает полезной, когда алгоритм работает быстро на достаточно большом подмножестве, Но не на всем множестве входных данных. Например, есть алгоритмы, которые работают значительно быстрее, если длина входных данных является простым числом, а не («к примеру») четным чнслом. В этом случае невозможно получить хорошую нижнюю границу времени выполнения, справедливую для всех $n < n_0\,\!$ .

Для проверки того, что $T(n)=n^3+2n^2\,\!$ есть $\Omega(n^3)\,\!$ , достаточно положить $c=1\,\!$ . Тогда $T(n)>cn^3\,\!$ для $n=0,1,...\,\!$ .

Для другого примера положим, что $T(n)=n\,\!$ для нечетных $n\ge1\,\!$ и $T(n)={n^2\over100}\,\!$ — для четных $n\ge0\,\!$ . Для доказательства того, что $T(n)\,\!$ есть $\Omega(n^2)\,\!$ , достаточно положить $c=\frac{1}{100}\,\!$ и рассмотреть множество четных чисел $\pi=0,2,4,6,...\,\!$ .

[править] Время выполнения алгоритма

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

Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимости программы, т.е. фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наиболее простой для реализации.
Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения. Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов.
Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Категории: Алгоритмы | Теория алгоритмов | Анализ алгоритмов