Готовимся к ЕГЭ по информатике

Сложность алгоритма

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

• O(k*f)=O(f)
• O(f*g)=O(f)*O(g) или O(f/g)=O(f)/O(g)
• O(f+g) равна доминанте O(f) и O(g)

Здесь k обозначает константу, a f и g – функции.
Первое правило, приведенное на рисунке, декларирует, что постоянные множители не имеют значения для определения порядка сложности.
5*N=O(N)
Из второго правила следует, что порядок сложности произведения двух функций равен произведению их сложностей.
O((17*N)*N) = O(17*N)*O(N) = O(N)*O(N)=O(N*N) = O(N²)
Из третьего правила следует, что порядок сложности суммы функций определяется как порядок доминанты первого и второго слагаемых, т.е. выбирается наибольший порядок.
O(N⁵+N²)=O(N⁵)
Наиболее часто встречаемые оценки временной сложности:

Эффективный алгоритм – это тот, который решает задачу за меньшее время.
Пример 1: Пусть есть два алгоритма А1 и А2, решающих одну и ту же задачу. Первый алгоритм решает задачу размерности N=10⁶ за N² операций, а второй – за 10*N*LogN. Первый алгоритм выполняется на суперкомпьютере с быстродействием 10⁸ операций в секунду, а второй – на простом, с быстродействием 10⁶ операций в секунду. Время решения задачи в том и в другом случаях: t1 = 10¹²/10⁸ ~2,8 часа; t2 = (6*10⁷*Log10)/10⁶ ~200 секунд. t1 больше чем t2 в 50,4 раза.
Пример 2: Поиск максимального элемента в одномерном массиве за N-1 сравнение мы легко реализовать.
…
Min:=A[1];
For i:=2 To N Do If A[i]<Min Then Min:=A[i];
…
Если необходимо найти и минимальный элемент, решение за t1 = 2*N-2 операций сравнения очевидно, но можно улучшить результат.
…
If A[1]>A[2] Then Begin Max:=A[1]; Min:=A[2]; End
Else Begin Min:=A[1]; Max:=A[2]; End;
i:=3;
While i<=N-1 Do Begin
If A[i]>A[i+1] Then
Begin
If A[i]>Max Then Max:=A[i];
If A[i+1]<Min Then Min:=A[i+1];
End;
Else
Begin
If A[i+1]>Max Then Max:=A[i+1];
If A[i]<Min Then Min:=A[i];
End;
End;
Inc(i,2);
End;
…
На каждую пару чисел, кроме первой, требуется три сравнения. На первую – одно. Время решения t2 = 3*[N/2]-2 (в количестве операций сравнения), где символами обозначено ближайшее целое число, превышающее значение N/2. Для сравнения методов можно найти разность t1-t2, например, при N=109 t1-t2= (2*109-2)-(3*[109/2]-2)= 1999999998-1499999998=500000000. Таким образом, использование второго решения выгоднее, т.к. выполняется на 500000000 операций сравнения меньше.
Одним из основных приемов решения задач является реализация принципа «разделяй и властвуй», т.е. задача разбивается на подзадачи, решаемые независимо, а затем результаты объединяются. Пусть размерность задачи описывается значением N. Нам необходимо оценить время решения T(N). Сложность задачи обычно определяется числом и размером подзадач и в меньшей степени действиями, необходимыми для разбиения задачи на подзадачи. Теорема приведенная ниже, является основой оценки времени решения задач при использовании принципа «разделяй и властвуй».
Теорема: Пусть a, b, c – неотрицательные постоянные.
Решение уравнений:

• T(N)=b, при N=1,
• T(N)=a*T(N/c)+b*N, при N>1, где N – степень числа c, имеет вид:
• T(N)=O(N), если a<c,
• T(N)=O(N*LogN), если a=c,
• T(N)=O(Nlogca), если a>c.

Существуют два способа анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних и внутренним). Для примера можно рассмотреть оценку сложность программы:
Пример 3: "Тройки Пифагора"

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(доминантыусловия)=О(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O(N²);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N²)= O(N³);
O(D)=O(A)+O(E)=O(1)+ O(N³)= O(N³)
Сложность данного алгоритма O(N³).
Как правило, около 90% времени работы программы требует выполнение повторений и только 10% составляют непосредственно вычисления. Анализ сложности программ показывает, на какие фрагменты выпадают эти 90% -это циклы наибольшей глубины вложенности. Повторения могут быть организованы в виде вложенных циклов или вложенной рекурсии.
Эта информация может использоваться программистом для построения более эффективной программы следующим образом. Прежде всего можно попытаться сократить глубину вложенности повторений. Затем следует рассмотреть возможность сокращения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет выполнение внутренних циклов, то 30%-ное сокращение этих небольших секций приводит к 90%*30%=27%-му снижению времени выполнения всей программы.
Пример 4: Оценка алгоритма бинарного поиска в массиве – дихотомии.
Суть алгоритма: идем к середине массива и ищем соответствие ключа значению срединного элемента. Если нам не удается найти соответствия, мы смотрим на относительный размер ключа и значение срединного элемента и затем перемещаемся в нижнюю или верхнюю половину списка. В этой половине снова ищем середину и опять сравниваем с ключом. Если не получается, снова делим на половину текущий интервал.
…
Function search(low, high, key: integer): integer;
Var
mid, data: integer;
Begin
While low<=high Do
Begin
mid:=(low+high) div 2;
data:=a[mid];
If key=data Then
search:=mid
Else
If key<data Then
high:=mid-1
Else
low:=mid+1;
End;
search:=-1;
End;
…
Решение:
Первая итерация цикла имеет дело со всем списком. Каждая последующая итерация делит пополам размер подсписка. Так, размерами списка для алгоритма являются
n n/2¹ n/2² n/2³ n/2⁴ ... n/2^m
В конце концов будет такое целое m, что
n/2^m<2 или n<2^m+1
Так как m - это первое целое, для которого n/2^m<2, то должно быть верно
n/2^m-1>=2 или 2^m=<n
Из этого следует, что
2^m=<n<2m+1
Возьмем логарифм каждой части неравенства и получим
m=<log₂n=x<m+1
Значение m - это наибольшее целое, которое =<х.
Итак, O(Log₂n).
Обычно решаемая задача имеет естественный "размер" (обычно количество данных ею обрабатываемых) которое мы называем N. В конечном итоге нам бы хотелось получить выражение для времени, необходимого программе для обработки данных размера N, как функцию от N. Обычно наc интересует средний случай – ожидаемое время работы программы на "типичных" входных данных, и худший случай – ожидаемое время работы программы на самых плохих входных данных.
O-анализ сложности получил широкое распространение во многих практических приложениях. Тем не менее необходимо четко понимать его ограниченность.
К основным недостаткам подхода можно отнести следующие:
для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно,
часто трудно определить сложность "в среднем",
O-оценки слишком грубые для отображения более тонких отличий алгоритмов,
O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.
Определение сложности в O-обозначениях – далеко нетривиальная задача. В частности, эффективность двоичного поиска определяется не глубиной вложенности циклов, а способом выбора каждой очередной попытки.
Еще одна сложность – определение "среднего случая". Обычно сделать это достаточно трудно из-за невозможности предсказания условий работы алгоритма. Иногда алгоритм используется как фрагмент большой, сложной программы. Иногда эффективность работы аппаратуры и/или операционной системы, или некоторой компоненты компилятора существенно влияет на сложность алгоритма. Часто один и тот же алгоритм может использоваться в множестве различных приложений.
Из-за трудностей, связанных с проведением анализа временной сложности алгоритма "в среднем", часто приходится довольствоваться оценками для худшего и лучшего случаев. Эти оценки по сути определяют нижнюю и верхнюю границы сложности "в среднем". Собственно, если не удается провести анализ сложности алгоритма "в среднем", остается следовать одному из законов Мерфи, согласно которому оценка, полученная для наихудшего случая, может служить хорошей аппроксимацией сложности "в среднем".
Возможно, основным недостатком O-функций является их чрезмерная грубость. Например, если алгоритм A выполняет некоторую задачу за 0.001*N секунд, в то время как для ее же решения с помощью алгоритма A требуется 1000*N секунд, то B в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N).
Существуют еще и интеллектуальная форма сложности. При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки.
Все три формы сложности обычно взаимосвязаны. Как правило, при разработке алгоритма с хорошей временной оценкой сложности приходится жертвовать его пространственной и/или интеллектуальной сложностью. Например, алгоритм быстрой сортировки существенно быстрее, чем алгоритм сортировки выборками.