• Главная
  •  > 
  • Игры
  •  > 
  • Принципы определения сложности алгоритма поиска. Временная сложность при логарифмическом весовом критерии

Принципы определения сложности алгоритма поиска. Временная сложность при логарифмическом весовом критерии

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A;
for j:=1 to N do
begin
if A>max then
max:=A
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2)*O(N^3)=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2)+O(N^3)=O(N^3). Следующий фрагмент имеет именно такую сложность:
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{какое-то действие}
end;
procedure Both;
begin
Fast;
Slow;
end;
Сложность рекурсивных алгоритмов
Простая рекурсия
Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).
Многократная рекурсия
Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.
Объёмная сложность рекурсивных алгоритмов
Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур.
Средний и наихудший случай
Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.
Общие функции оценки сложности
Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0 5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

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

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

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

Определения

Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа .
Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.

Существуют понятия сложности в худшем , среднем или лучшем случае . Обычно, оценивают сложность в худшем случае.

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

Порядок роста сложности алгоритмов

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

Шаг алгоритма – совокупность последовательно-расположенных элементарных операций, время выполнения которых не зависит от размера входа, то есть ограничена сверху некоторой константой.

Виды асимптотических оценок

O – оценка для худшего случая

Рассмотрим сложность f(n) > 0 , функцию того же порядка g(n) > 0 , размер входа n > 0 .
Если f(n) = O(g(n)) и существуют константы c > 0 , n 0 > 0 , то
0 < f(n) < c*g(n),
для n > n 0 .

Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.

Примеры асимптотических функций
f(n) g(n)
2n 2 + 7n - 3 n 2
98n*ln(n) n*ln(n)
5n + 2 n
8 1
Ω – оценка для лучшего случая

Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n)) , если
0 < c*g(n) < f(n)


Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.

Θ – оценка для среднего случая

Стоит лишь упомянуть, что в данном случае функция f(n) при n > n 0 всюду находится между c 1 *g(n) и c 2 *g(n) , где c – константный множитель.
Например, при f(n) = n 2 + n ; g(n) = n 2 .

Критерии оценки сложности алгоритмов

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

Временная сложность при ЛВК определяется значением l(O p) , где O p – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M) , где M – величина ячейки памяти.

Пример оценки сложности при вычислении факториала

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

Void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }

Временная сложность при равномерном весовом критерии

Достаточно просто определить, что размер входа данной задачи – n .
Количество шагов – (n - 1) .

Таким образом, временная сложность при РВК равна O(n) .

Временная сложность при логарифмическом весовом критерии

В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.

Итак, в данной задаче выделяется три операции:

1) i <= n

На i-м шаге получится log(n) .
Так как шагов (n-1) , сложность данной операции составит (n-1)*log(n) .

2) i = i + 1

На i-м шаге получится log(i) .
.

3) result = result * i

На i-м шаге получится log((i-1)!) .
Таким образом, получается сумма .

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

Ёмкостная сложность при равномерном весовом критерии

Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
Так как количество переменных не зависит от размера входа, сложность будет равна O(1) .

Ёмкостная сложность при логарифмическом весовом критерии

В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение V max .
В данной задаче существует переменная, значение которой не превосходит n (i) , и переменная, значение которой не превышает n! (result) . Таким образом, оценка равна O(log(n!)) .

Выводы

Изучение сложности алгоритмов довольно увлекательная задача. На данный момент анализ простейших алгоритмов входит в учебные планы технических специальностей (если быть точным, обобщённого направления «Информатика и вычислительная техника»), занимающихся информатикой и прикладной математикой в сфере IT.
На основе сложности выделяются разные классы задач: P , NP , NPC . Но это уже не проблема теории асимптотического анализа алгоритмов.

При проектировании алгоритмов, как правило, не представляет интереса точное число шагов, необходимых для решения задачи на конкретном наборе данных. Гораздо важнее знать, как будет изменяться время решения задачи T, если размер входа n растёт.

Класс алгоритмов, время работы которых растёт, по крайней мере, так же быстро, как некоторая функция f(n), обозначается как Ω(f(n)). Это означает, что при всех n, превышающих порог n 0 , T(n) ≥C . f(n) для некоторого положительного числаC. Оценка времени работы снизу может представлять интерес только как теоретическая нижняя граница эффективности любого алгоритма для некоторой задачи, которую преодолеть невозможно.

Класс алгоритмов, время работы которых растёт не быстрее функции f(n), обозначается O (f(n)), что означает существование положительных чисел n 0 и c таких, что при n > n 0 T(n) ≤C . f(n). Этот класс - важнейшая характеристика алгоритма, еговременная сложность . По скорости роста этого времени в зависимости от размера входа алгоритмы делятся на следующие классы временной сложности:

Алгоритмы константной сложности - T(n) ∈ O(1);

Логарифмической сложности - T(n) ∈ O(log n);

Линейной сложности - T(n) ∈ O(n);

Квадратичной сложности - T(n) ∈ O(n 2);

Кубической сложности - T(n) ∈ O(n 3);

Полиномиальной сложности - T(n) ∈ O(n k), где k = const; k = 0, 1, 2 или 3 - это частные случаи классов полиномиальной сложности;

Экспоненциальной сложности - T(n) ∈ O(a n).

Очевидно, что классы в этом перечне упорядочены по возрастанию мощности. Так, класс O (1) является подмножеством любого из остальных классов. Задача программиста - найти или разработать алгоритм класса минимально возможной мощности и реализовать его так, чтобы оценка временной сложности не ухудшилась.

Алгоритм, для которого оценки Ω(f(n) и O (f(n)) совпадают, называетсяоптимальным . Так, очевидно, что алгоритм, имеющий на входе некоторое множество, будет оптимальным, если его временная сложностьO (1). Такой алгоритм можно попытаться найти, если задача не требует рассмотреть множество целиком. Если же требуется что-то сделать с каждым элементом множества мощностью n, оптимальный алгоритм будет иметь сложностьO (n). Если имеется два множества, и нужно обработать все возможные пары их элементов, можно ожидать сложностиO (n 2), для трёх множеств, если обрабатываются все тройки -O (n 3), и т. д.

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

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

Для самого неудобного набора данных - сложность «в худшем случае»;

Для типового набора данных - сложность «в среднем».

Тривиальные входные данные («лучший случай») обычно интереса не представляют.

Для оценки временной сложности по реализации алгоритма (тексту программы) можно руководствоваться следующими соображениями:

Операции присваивания (копирования) и проверки условия для базовых типов данных выполняются за константное время. Если при этом вызывается функция, сложность шага алгоритма определяется сложностью функции (в операциях с объектами функции могут вызываться неявно);

Сложность алгоритма, состоящего из последовательности шагов, определяется по самому сложному шагу;

Сложность выбора по условию определяется по самой сложной из альтернатив. В порядке исключения можно не принимать во внимание альтернативы, выбираемые очень редко. Можно учесть такие альтернативы, как «худший случай»;

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

Рекурсия рассматривается как тот же цикл. Её сложность определяется как произведение сложности одного вызова функции на количество вызовов.

Пример 1. Вычислить b = (a∈A), где множество A мощностью nA представлено массивом целых чисел.

Решение : b = false; for (i = 0; !b && (i < nA); i++) b |= (a == A[i]);

Временная сложность алгоритма - O (nA). Если элемент a найден, алгоритм прекращает работу, выполнив от 1 до nA шагов. В среднем количество шагов будет nA / 2, в худшем случае (a∉A) - nA.

Пример 2. Вычислить C = A⋂B для множеств, представленных неупорядоченными массивами.

Решение : проверяем все возможные пары элементов двух множеств и отбираем совпадения.

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

Проверка на совпадение и присваивание выполняются за константное время, поэтому сложность алгоритма - O (nA × nB), илиO (n 2), где n - средняя мощность множеств.

Пример 3. Вычислить D = A⋂ B⋂ C.

Очевидное решение

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++)

for (r = 0; r

if ((A[ i ] == B[ j ]) && (A[ i ] == C[ r ])) D[ k++ ] = A[ i ];

имеет временную сложность O (n 3), поскольку перебираются все возможные тройки. Однако перебирать все тройки никакой необходимости нет.

Модифицируем алгоритм:

for(i=k= 0;i

for (j = 0; j < nB; j++)

if (A[i] == B[j]) for (r = 0; r

if (A[i] == C[r]) D = A[i];

В алгоритме по-прежнему три вложенных цикла, но внутренний цикл теперь зависит от условия A[ i ] == B[ j ], которое проверяется n 2 раз, но удовлетворяется не более чем n раз, т. е. рассматриваются только такие тройки, у которых первые два элемента совпадают. Проверка A[i] == C[r] выполняется, таким образом, не более n 2 раз, и общая сложность алгоритма - O (n 2).

Пример 4. Вычислить C = A⋂B для множеств, представленных строками символов.

Решение :

for(i = k = 0; i < strlen(A); i++)

for (j = 0; j < strlen(B); j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

По аналогии с примером 2 можно оценить сложность как O (n 2). Однако это неверно, так как в обоих циклах по n раз вычисляется функция определения длины строки strlen(), которая, очевидно, подсчитывает в строке количество символов до ближайшего нуля перебором, т. е. имеет линейную сложность. Вычисление этой функции - один из шагов внутренней части обоих циклов. Таким образом, внутренняя часть вложенного цикла состоит из трёх шагов, двух константных (проверка и присваивание) и линейного (вычисление функции). С учётом n повторений сложность всего цикла -O (n 2). Внешний цикл добавляет сюда ещё шаг вычисления функции сложностьюO (n). Сложность его внутренней части -O (n 2), а всего алгоритма -O (n 3)! Это - цена экономии двух целых переменных. На самом деле нужно вычислить nA = strlen(A); nB = strlen(B), а затем использовать алгоритм из примера 2.

Редактор Г. Г. Петров

Подписано в печать. Формат 60×84 1/16.

Бумага офсетная. Печать офсетная. Печ. л. 4,0.

Гарнитура «Times». Тираж экз. Заказ

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Издательство СПбГЭТУ «ЛЭТИ»

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A;
for j:=1 to N do
begin
if A>max then
max:=A
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2)*O(N^3)=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2)+O(N^3)=O(N^3). Следующий фрагмент имеет именно такую сложность:
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{какое-то действие}
end;
procedure Both;
begin
Fast;
Slow;
end;
Сложность рекурсивных алгоритмов
Простая рекурсия
Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).
Многократная рекурсия
Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.
Объёмная сложность рекурсивных алгоритмов
Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур.
Средний и наихудший случай
Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.
Общие функции оценки сложности
Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0 5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату .

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

Модель RAM (Random Access Machine)

Каждое вычислительное устройство имеет свои особенности, которые могут влиять на длительность вычисления. Обычно при разработке алгоритма не берутся во внимание такие детали, как размер кэша процессора или тип многозадачности, реализуемый операционной системой. Анализ алгоритмов проводят на модели абстрактного вычислителя, называемого машиной с произвольным доступом к памяти (RAM).

Модель состоит из памяти и процессора, которые работают следующим образом:

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

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

Подсчет операций. Классы входных данных

Одним из способов оценки трудоемкости (\(T_n\)) является подсчет количества выполняемых операций . Рассмотрим в качестве примера алгоритм поиска минимального элемента массива.

Начало; поиск минимального элемента массива array из N элементов min:= array для i от 2 до N выполнять: если array[i] < min min:= array[i] конец; вернуть min

При выполнении этого алгоритма будет выполнена:

  1. N — 1 операция присваивания счетчику цикла i нового значения;
  2. N — 1 операция сравнения счетчика со значением N;
  3. N — 1 операция сравнения элемента массива со значением min;
  4. от 1 до N операций присваивания значения переменной min.

Точное количество операций будет зависеть от обрабатываемых данных, поэтому имеет смысл говорить о наилучшем, наихудшем и среднем случаях. При этом худшему случаю всегда уделяется особое внимание, в том числе потому, что «плохие» данные могут быть намеренно поданы на вход злоумышленником.

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

  1. исходные данные разбиваются на группы так, что трудоемкость алгоритма (\(t_i\)) для любого набора данных одной группы одинакова;
  2. исходя из доли наборов данных группы в общем числе наборов, рассчитывается вероятность для каждой группы (\(p_i\));
  3. оценка среднего случая вычисляется по формуле: \(\sum\limits_{i=1}^m p_i\cdot t_i\).

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

Подсчет количества операций позволяет сравнить эффективность алгоритмов. Однако, аналогичный результат можно получить более простым путем. Анализ проводят с расчетом на достаточно большой объем обрабатываемых данных (\(n \to \infty \)), поэтому ключевое значение имеет скорость роста функции сложности , а не точное количество операций.

При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции \(f_x = 10 \cdot x^2 + 20 \) и \(g_x = x^2\) эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.

В оценке алгоритмов используются специальные асимптотические обозначения , задающие следующие классы функций :

  • \(\mathcal{O}(g)\) — функции, растущие медленнее чем g;
  • \(\Omega(g)\) — функции, растущие быстрее чем g;
  • \(\Theta(g)\) — функции, растущие с той же скоростью, что и g.

Запись \(f_n = \mathcal{O}(g_n)\) означает принадлежность функции f классу \(\mathcal{O}(g)\), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. \(\exists n_0 > 0, c > 0: \forall n > n_0, f_n \leq c \cdot g_n\).

Ограниченность функции g снизу функцией f записывается следующим образом: \(g_n =\Omega(f_n)\). Нотации \(\Omega\) и \(\mathcal{O}\) взаимозаменяемы: \(f_n = \mathcal{O}(g_n) \Leftrightarrow g_n =\Omega(f_n)\).

Асимптотические обозначения «О большое» и «Омега большое»

Если функции f и g имеют одинаковую скорость роста (\(f_n = \Theta(g_n)\)), то существуют положительные константы \(c_1\) и \(c_2\) такие, что \(\exists n_0 > 0: \forall n > n_0, f_n \leq c_1 \cdot g_n, f_n \geq c_2 \cdot g_n\). При этом \(f_n = \Theta(g_n) \Leftrightarrow g_n = \Theta(f_n)\).


Асимптотическое обозначение «Тета большое»

Примеры анализа алгоритмов

Алгоритм поиска минимального элемента массива , приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность \(T^{iter} = \mathcal{O}(1)\). В связи с этим, верхняя оценка всего алгоритма \(T^{min}_n = \mathcal{O}(n) \cdot \mathcal{O}(1) = \mathcal{O}(n \cdot 1) = \mathcal{O}(n)\). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать \(T^{min}_n = \Theta(n) \).

Алгоритм пузырьковой сортировки (bubble sort) использует два вложенных цикла. Во внутреннем последовательно сравниваются пары элементов и если оказывается, что элементы стоят в неправильном порядке — выполняется перестановка. Внешний цикл выполняется до тех пор, пока в массиве найдется хоть одна пара элементов, нарушающих требуемый порядок .

Начало; пузырьковая сортировка массива array из N элементов nPairs:= N; количество пар элементов hasSwapped:= false; пока что ни одна пара не нарушила порядок для всех i от 1 до nPairs-1 выполнять: если array[i] > array то: swap(array[i], array); обменять элементы местами hasSwapped:= true; найдена перестановка nPairs:= nPairs - 1; наибольший элемент гарантированно помещен в конец если hasSwapped = true - то перейти на п.3 конец; массив array отсортирован

Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как \(T^{swap} = \Theta(1) \). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.

Таким образом:

  • \(T^{bubble}_n = \mathcal{O}(\sum\limits_{i=1}^n \sum\limits_{j=1}^{n-i} 1) = \mathcal{O}(\sum\limits_{i=1}^n n) = \mathcal{O}(n ^2)\);
  • \(T^{bubble}_n = \Omega(1 \cdot \sum\limits_{j=1}^{n-i} 1) = \Omega(n)\).

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

Начало; selection_sort - сортировка массива array из N элементов методом выбора для всех i от 1 до N выполнять: imin:= indMin(array, N, i) swap(array[i], array) конец; массив array отсортирован

Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: \(T^{indMin}_{n, i} = \Theta(n — i)\).

У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: \(T^{select}_n = \Theta(\sum\limits_{i=1}^{n} (T^{indMin}_{n, i} + T^{swap})) =\Theta(\sum\limits_{i=1}^{n} (n-i)) = \Theta(\frac{n-1}{2} \cdot n) = \Theta(n^2) \).

Математический аппарат анализа алгоритмов

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

Формулы суммирования

В примерах, рассмотренных выше, мы уже сталкивались с нетривиальными формулами суммирования. Чтобы дать оценку суммы можно использовать ряд известных тождеств:

  • вынос постоянного множителя за знак суммы: \(\sum\limits_{i=1}^{n} (c \cdot f_i) = c \cdot \sum\limits_{i=1}^{n} \cdot f_i\);
  • упрощение суммы составного выражения: \(\sum\limits_{i=1}^{n} (f_i + g_i) = \sum\limits_{i=1}^{n} (f_i) + \sum\limits_{i=1}^{n} (g_i)\);
  • сумма чисел арифметической прогрессии: \(\sum\limits_{i=1}^{n} (i^p) = \Theta(n^{p+1})\);
  • сумма чисел геометрической прогрессии: \(\sum\limits_{i=0}^{n} (a^i) = \frac {a \cdot (a^{n+1} — 1)}{a — 1}\). При \(n \to \infty \) возможны 2 варианта:
    • если a < 1, то сумма стремится к константе: \(\Theta(1)\);
    • если a > 1, то сумма стремится к бесконечности: \(\Theta(a^{n+1})\);
    • если a = 0, формула неприменима, сумма стремится к N: \(\Theta(n)\);
  • логарифмическая сложность алгоритма: \(\sum\limits_{i=1}^{n} \frac{1}{i} = \Theta(\log n)\);
  • сумма логарифмов: \(\sum\limits_{i=1}^{n} \log i = \Theta(n \cdot \log n)\).

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

Суммирование и интегрирование

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

На рисунках приведен пример аппроксимации функции \(f_x = \log x\) левыми и правыми прямоугольниками. Очевидно, они дадут верхнюю и нижнюю оценку площади под графиком:

  • \(\int\limits_a^n f_x dx \leq \sum\limits_{i=a }^{n} f_i \leq \int\limits_{a+1}^{n+1} f_x dx\) для возрастающих функций;
  • \(\int\limits_a^n f_x dx \geq \sum\limits_{i=a }^{n} f_i \geq \int\limits_{a+1}^{n+1} f_x dx\) для убывающих функций.

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

Сравнение сложности алгоритмов. Пределы

Сложность алгоритмов определяется для больших объемов обрабатываемых данных, т.е. при \(n\to\infty\). В связи с этим, при сравнении трудоемкости двух алгоритмов можно рассмотреть предел отношения функций их сложности : \(\lim\limits_{n \to \infty} \frac {f_n}{g_n}\). В зависимости от значения предела возможно сделать вывод относительно скоростей роста функций:

  • предел равен константе и не равен нулю, значит функции растут с одной скоростью:\(f_n = \Theta(g_n)\);
  • предел равен нулю, следовательно \(g_n\) растет быстрее чем \(f_n\): \(f_n = \mathcal{O}(g_n)\);
  • предел равен бесконечности, \(g_n\) растет медленнее чем \(f_n\): \(f_n = \Omega(g_n)\).

Если функции достаточно сложны, то такой прием значительно упрощает задачу, т.к. вместо предела отношения функций можно анализировать предел отношения их производных (согласно правилу Лопиталя ): \(\lim\limits_{n \to \infty} \frac {f_n}{g_n} = \lim\limits_{n \to \infty} \frac {f’_n}{g’_n}\). Правило Лопиталя можно использовать если функции обладают следующими свойствами:

  • \(\lim\limits_{n \to \infty} \frac {f_n}{g_n} = \frac{0}{0} или \frac {\infty}{\infty} \);
  • \(f_n \) и \(g_n\) дифференцируемы;
  • \(g’_n \ne 0 \) при \(n \to \infty\);
  • \(\exists \lim\limits_{n \to \infty} \frac {f’_n}{g’_n}\).

Допустим, требуется сравнить эффективность двух алгоритмов с оценками сложности \(\mathcal{O}(a^n)\) и \(\mathcal{O}(n^b)\), где a и b — константы. Известно, что \((c^x)’ =c^x \cdot ln(c)\), но \((x^c)’ = c \cdot x^{c-1} \). Применим правило Лопиталя к пределу отношения наших функций b раз, получим: \(\lim\limits_{n \to \infty} \frac {\mathcal{O}(a^n)}{\mathcal{O}(n^b)} = \lim\limits_{n \to \infty} \frac {\mathcal{O}(a^n * ln^b (a))}{\mathcal{O}(b!)} = \infty\). Значит функция \(a^n\) имеет более высокую скорость роста. Без использования пределов и правила Лопиталя такой вывод может казаться не очевидным.

Логарифмы и сложность алгоритмов. Пример

По определению \(\log_a{x} = b \Leftrightarrow x = a^b\). Необходимо знать, что \(x \to \infty \Rightarrow \log_a{x} \to \infty\), однако, логарифм — это очень медленно растущая функция . Существует ряд формул, позволяющих упрощать выражения с логарифмами:

  • \(\log_a{x \cdot y} = \log_a{x} + \log_a{ y}\);
  • \(\log_a{x^b} = b \cdot \log_a{ x}\);
  • \(\log_a{x} =\frac{\log_b{x}}{\log_b{a}}\).

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

Логарифмической сложностью обладают алгоритмы, для которых не требуется обрабатывать все исходные данные, они используют принцип «разделяй и властвуй». На каждом шаге часть данных (обычно половина) отбрасывается. Примером может быть функция поиска элемента в отсортированном массиве (двоичного поиска):

Начало; поиск элемента E в отсортированном по возрастанию массиве array из N элементов left:= 1, right:= N; левая и правая граница, в которых находится искомый элемент выполнять пока left =< right: mid:= (right + left) div 2; вычисление индекса элемента посередине рассматриваемой части массива если array = E конец; вернуть true (элемент найден) если array < E; искомый элемент больше середины, значит все элементы левее mid можно отбросить left:= mid + 1; иначе right:= mid конец; вернуть false (элемент не найден)

Очевидно, что на каждом шаге алгоритма количество рассматриваемых элементов сокращается в 2 раза. Количество элементов, среди которых может находиться искомый, на k-том шаге определяется формулой \(\frac{n}{2^k}\). В худшем случае поиск будет продолжаться пока в массиве не останется один элемент, т.е. чтобы определить количество итераций для верхней оценки, достаточно решить уравнение \(1 = \frac{n}{2^k} \Rightarrow 2^i = n \Rightarrow i = \log_2 n\). Следовательно, алгоритм имеет логарифмическую сложность: \(T^{binSearch}_n = \mathcal{O}(\log n)\).

Результаты анализа. Замечания

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

Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:

  • алгоритм поиска элемента в неупорядоченном массиве не может иметь верхнюю оценку сложности лучше, чем \(\mathcal{O}(n)\). Это связано с тем, что невозможно определить отсутствие элемента в массиве (худший случай) не просмотрев все его элементы;
  • возможно формально доказать, что не возможен алгоритм сортировки произвольного массива, работающий лучше чем \(\mathcal{O}(n \cdot \log n)\) .

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

Список использованных источников

  1. – режим доступа: https://сайт/archives/578. Дата обращения: 06.01.2014.
  2. Васильев В. С. [Электронный ресурс] – режим доступа: https://сайт/archives/1462. Дата обращения: 06.01.2014.
  3. Дж. Макконелл . Активный обучающий подход. - 3-е дополненное издание. М: Техносфера, 2009. -416с.
  4. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.
  5. Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. - СПб.: БХВ-Петербург. 2011. - 720 с.: ил.