05. Порядок роста сложности вычислений

---

ВПЕРЁД ⇒

Асимптотическая оценка сложности вычислений

⇐ НАЗАД

Модель вычислений

---

Порядок роста сложности вычислений

$T(n)$ - сложность вычислений (время работы) алгоритма, представляющая собой функцию количества операций $T$ от размера входных данных $n$.

В функции времени работы $T$ от размера входных данных $n$ нас, в первую очередь, интересует сам характер зависимости, то есть является ли эта зависимость линейной, или нелинейной (например, степенной, экспоненциальной и т.п.).

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

Рассмотрим, для примера, полиномиальную зависимость $T(n)=k_1{n}^3+k_2{n}^2+k_{3}n+k_4$. Мы хотим определить характер этой зависимости. Для этого необходимо избавиться от всех слагаемых, которые с бесконечным ростом параметра $n$ начинают вносить пренебрежительно малый вклад в эту зависимость. Тем самым мы упростим рассматриваемую зависимость. Благодаря упрощению зависимости, по оставшимся слагаемым мы сможем легко определить, как на самом деле ведёт себя эта зависимость. Наибольший вклад в характер полиномиальной зависимости вносит самый старший член полинома. Докажем это.

Поскольку мы утверждаем, что в $k_1{n}^3+k_2{n}^2+k_{3}n+k_4$ старший член (полином) $k_1{n}^3$ вносит наибольший вклад в поведение зависимости, то это означает, что полином $k_1{n}^3$ с ростом параметра $n$ должен расти быстрее, чем полином $k_2{n}^2+k_{3}n+k_4$, причём отношение первого полинома ко второму будет увеличиваться до бесконечности по мере бесконечного увеличения параметра $n$. И это действительно так. Рассмотрим отношение двух указанных полиномов:

$\frac{k_1{n}^3}{k_2{n}^2+k_{3}n+k_4}=\frac{k_1{n}^3}{n^2(k_2+\frac{k_3}{n}+\frac{k_4}{n^2})}=\frac{k_{1}n}{k_2+\frac{k_3}{n}+\frac{k_4}{n^2}}$.

Очевидно, что с бесконечным ростом параметра $n$ дробь $\frac{k_{1}n}{k_2+\frac{k_3}{n}+\frac{k_4}{n^2}}$ также бесконечно растёт:

• $k_{1}n$ стремится к бесконечности;
• поскольку $\frac{k_3}{n}$ и $\frac{k_4}{n^2}$ стремятся к нулю, то $k_2+\frac{k_3}{n}+\frac{k_4}{n^2}$ стремится к $k_2$.

Таким образом, для $n$, стремящегося к плюс бесконечности, получаем, что $\frac{k_1{n}^3}{k_2{n}^2+k_{3}n+k_4}=\frac{+\infty }{k_2}=+\infty$.

У старшего члена исходного полинома $k_1{n}^3+k_2{n}^2+k_{3}n+k_4$ (то есть у выражения $k_1{n}^3$) конкретное значение множителя $k_1$ нам не важно, так как оно оценивается в некотором приближении, то есть фактическое значение множителя может отличаться от оценённого. Например, в зависимости от используемого процессором набора инструкций, одни и те же операции разными процессорами могут выполняться за различное количество инструкций/тактов, поэтому мы можем лишь только предполагать, какие на самом деле значения множителей в слагаемых имеет полином. Таким образом, в рассматриваемой функции $T(n)=k_1{n}^3+k_2{n}^2+k_{3}n+k_4$ нас будет интересовать только старший член полинома без множителя (то есть $n^3$), как дающий наибольший вклад в сложность вычислений и называемый порядком роста (order of growth), или, как ещё говорят, скоростью роста (rate of growth) сложности вычислений.

Рассматривая входные данные достаточно больших размеров с целью получения оценки только лишь такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов. Это означает, что нас интересует только то, как время работы алгоритма растёт в пределе (то есть с увеличением размера входных данных до бесконечности).

В разделе математики, занимающимся анализом пределов (то есть бесконечно малых/больших величин) и называемом математическим анализом, для предельных величин существует специальное обозначение lim, что является сокращением от слова limit (на русский язык переводится какпредел):

• $\underset{x\to +\infty }{\lim }f(x)$ - значение функции $f(x)$ при $x$ , стремящемся к плюс бесконечности;
• $\underset{x\to -\infty }{\lim }f(x)$ - значение функции $f(x)$ при $x$ , стремящемся к минус бесконечности;
• $\underset{x\to 0}{\lim }f(x)$ - значение функции $f(x)$ при $x$ , стремящемся к нулю.

Таким образом, когда мы говорим, что изучаем асимптотическую эффективность алгоритма, то это означает, что нас интересует значение времени работы алгоритма $T(n)$ при размере входных данных $n$, стремящемся к плюс бесконечности, и это время мы можем записать как $\underset{n\to +\infty }{\lim }T(n)$.

Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких. Что это значит?

Представим, что у нас имеется два алгоритма, решающих одну и ту же задачу. Время работы первого алгоритма: $T_1(n)=n^2+10.000$. Время работы второго алгоритма: $T_2(n)=lo{g}_{10}(n)+\mathrm{2.000.000}$. Порядок роста сложности вычислений второго алгоритма равен $lo{g}_{10}(n)$ и ниже порядка роста сложности вычислений первого алгоритма ($n^2$). То есть второй алгоритм в асимптотическом смысле является более эффективным, чем первый алгоритм. Несмотря на то, что второй алгоритм эффективней первого, при малых значениях $n$ первый алгоритм будет выполняться быстрей второго алгоритма, например:

$$\begin{array}{rl}{T}_1(100)& =100^2+10.000=10.000+10.000=20.000;\\ T_2(100)& =lo{g}_{10}(100)+\mathrm{2.000.000}=2+\mathrm{2.000.000}=\mathrm{2.000.002};\\ T_1<T_2.& \end{array}$$

Однако, с ростом $n$, второй алгоритм рано или поздно начнёт выполняться быстрей первого алгоритма, например:

$$\begin{array}{rl}{T}_1(10000)& =10000^2+10.000=\mathrm{100.000.000}+10.000=\mathrm{100.010.000};\\ T_2(10000)& =lo{g}_{10}(10000)+\mathrm{2.000.000}=4+\mathrm{2.000.000}=\mathrm{2.000.004};\\ T_2<T_1.& \end{array}$$

Таким образом, при большом размере входных данных $n$, порядок роста алгоритма будет играть ключевую роль в сложности вычислений, и в вычислениях будет выигрывать тот алгоритм, чей порядок роста ниже.

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

Теперь рассмотрим конкретный пример: алгоритм поиска минимального элемента в массиве размерностью $n$.

Поиск минимального элемента в массиве

a[0..n-1] = [k1, …, kn] // $n$ операций присваивания начальных значений в массив

res = $+\infty$ // $1$ операция присваивания

for i = 0..n-1 // $2$ операции на итерацию: проверка, что i не превышает n-1, а также увеличение i на 1

res = min(res, a(i)) // $3$ операции на итерацию: сравнение; возврат результата из min() и его копирование в res

print(res) // $1$ операция вывода полученного минимального значения на экран

---

a[0..n-1] = [k1, …, kn] // $n$ операций

res = $+\infty$ // $1$ операция

for i = 0..n-1 // $2n+1$ операций, так как будет выполнено $n$ итераций,

// содержащих по 2 операции (сравнения и инкрементации),

// а в самом конце будет выполнена только одна операция

// сравнения, показывающая, что условие выхода из цикла

// достигнуто

res = min(res, a(i)) // $3n$ операций

print(res) // $1$ операция

Время работы алгоритма: $T(n)=6n+3$

Представленный алгоритм поиска минимального элемента в массиве никак не зависит от характера входных данных (данные могут быть как отсортированными в убывающем или возрастающем порядке, так и неотсортированными вовсе), то есть алгоритм работает одинаковым образом для всех возможных случаев входных данных. По этой причине полученная оценка $T(n)$ для времени работы алгоритма также не зависит от характера входных данных, то есть времена работ для наихудшего и наилучшего случаев входных данных совпадают. Под наихудшим случаем входных данных подразумеваются вариант входных данных, для которого алгоритм решения поставленной задачи будет отрабатывать медленней всего. Соответственно, под наилучшим случаем входных данных подразумеваются вариант входных данных, для которого алгоритм решения поставленной задачи будет отрабатывать быстрей всего.

При очень большом значении параметра $n$, в функции $T(n)$ можно пренебречь:

• слагаемым $+3$, как дающим наименьший вклад в сложность вычислений;
• множителем 6 старшего члена полинома ($6n$), так как этот множитель является только оценкой, и реальное значение этого множителя может быть совсем иным.

Исходя из сказанного, можем сделать вывод, что $n$ - порядок роста сложности вычислений алгоритма поиска минимального элемента в массиве размерностью $n$.

---

ВПЕРЁД ⇒

Асимптотическая оценка сложности вычислений

⇐ НАЗАД

Модель вычислений

---

Источники

• Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
• Томас Кормен “Алгоритмы. Построение и анализ”. Глава 2 “Приступаем к изучению”, параграф 2.2 “Анализ алгоритмов” (стр. 45-52).
• Томас Кормен “Алгоритмы. Построение и анализ”. Глава 3 “Рост функций” (стр. 67).

Категория

Алгоритмы-и-структуры-данных Алгоритмы-и-структуры-данных

Теги

• Алгоритм Алгоритм
• Время-работы Время-работы
• Сложность-по-времени Сложность-по-времени
• Временная-сложность Временная-сложность
• Time-complexity Time-complexity
• Сложность-вычислений Сложность-вычислений
• Асимптотическая-эффективность Асимптотическая-эффективность
• lim lim
• Limit Limit
• Предел Предел