Сложности в зависимости от выбранной. Оценка сложности алгоритмов, или Что такое О(log n). Общие функции оценки сложности
Типы алгоритмов. Сложность алгоритмов.
Алгоритмы
Под алгоритмом понимается описание последовательностидействий,необходимых для решения задачи (алгоритм не содержит описания данных и их структур, а описывает только действия).
Существует несколько форм описания алгоритмов:
1. словесное (для решения неформализованных задач)
2. запись с использованием математической либо другой специальной нотации
3. графическое изображение алгоритма
4. запись на метаязыке
5. запись на алгоритмическом языке
Название алгоритма может указывать либо на его назначение, либо на метод решения задачи.
Существует 2 типа алгоритмов: детерминированные и недетерминированные.
Детерминированные алгоритмы предполагают прямое решение задачи без использования повторов и выбора вариантов. Такой алгоритм не содержит элементов неопределённости. (Они всегда простые.)
Недетерминированные алгоритмы допускают повторы, выборы вариантов и использование метода проб и ошибок. Т.е. они содержат некоторый элемент неопределённости. Может использоваться такое понятие, как случайный выбор. Например, поиск оптимального маршрута через лабиринт, поисковый алгоритм нахождения экстремума ф-ции n переменных. (Это сложные алгоритмы.)
Для такого алгоритма невозможно даже сказать наперёд,будет ли получено решение при данном наборе входных данных.
Некоторые задачи могут быть решены с использованием обоих типов алгоритмов. Например, задача нахождения нужной строки в таблице. Если индекс строки известен, то алгоритм обращения к этой строке является детерминированным. Если индекс строки неизвестен заранее, то для нахождения строки может быть применён алгоритм случайного поиска (недетерминированный) (строка ищется по какому-то признаку и строки перебираются случайным образом). Такой способ эффективен для больших таблиц. Также может использоваться последовательный поиск перебором (II-й недетерминированный алгоритм). При таком методе строка будет найдена за 2n итераций (n-число строк). Последовательный поиск эффективен для малых объёмов.
Сложность алгоритма определяет зависимость времени работы алгоритма от объёма обрабатываемых данных.
Основные типы сложности алгоритмов:
1. Постоянная сложность – имеют алгоритмы, рассчитанные на обработку фиксированного объёма данных.
2. Линейная сложность (например, алгоритм обработки массива в памяти). Время работы такого алгоритма может быть оценено так: an+b, где n – количество элементов массива, a – время, необходимое для выполнения операций над отдельным элементом массива, b – время, затрачиваемое на выполнение вспомогательных операций.
3. Квадратичная сложность (например, алгоритм пузырьковой сортировки). (n-1) сравнений для определения I-го элемента,(n-2) – II-го элемента, (n-1)+(n-2)+…+3+2+1=. Для больших n время работы алгоритма ~.
Сложность алгоритма может оцениваться по уже написанной программе, для чего определяется число внутренних циклов.
Пример оценки сложности по тексту программы (алгоритм сортировки) :
Procedure сортировка;
For k:=1 to n-1 do
Min:=A(k); lok:=k;
For i:=k+1 to n do
If min>A(i) then
Min:=A(i); loc:=I;
A(loc):=A(k); A(k):=min
В данной прог-е внешний цикл исполняется n-1 раз, а внутренний исполняется в среднем раз.Общее число исполнений внутреннего цикла = 
. Для больших n количество исполнений ~. Т.е. алгоритм обладает квадратичной сложностью.
Оценка сложности алгоритма умножения 2-х матриц размерности n*n:
For i:=1 to n do
For j:=1 to n do
C(i,j):=0;
For k:=1 to n do
C(i,j):=C(i,j)+A(i,k)*B(k,j);
Сложность ~ (т.к. 3 цикла).
Замечание: Использование различных усовершенствований алгоритма не может привести к существенному изменению его оценки сложности. Изменение оценки сложности – индикатор того, что алгоритм изменился.
Можно дать формальное определение сложности алгоритма, используя нотацию «большого О» и понятие порядка функции. Считается, что 2 ф-ции f(n) и g(n) одного порядка, если для больших n существует константа k : . И формально такое высказывание записывается так: f(n)=O(g(n)).
Сложность алгоритмов обозначается:
O(n) – для алгоритмов линейного поиска
O() - для пузырьковой сортировки
O() - для перемножения матриц
O() - для двоичного поиска
Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.
Память или время
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 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
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! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.
Если для решения задачи существует один алгоритм, то можно придумать и много других алгоритмов для решения этой же задачи. Какой алгоритм лучше подходит для решения конкретной задачи? По каким критериям следует выбирать алгоритм из множества возможных? Как правило, мы высказываем суждение об алгоритме на основе его оценки исполнителем-человеком. Алгоритм кажется нам сложным, если даже после внимательного его изучения мы не можем понять, что же он делает. Мы можем назвать алгоритм сложным и запутанным из-за того, что он обладает разветвленной логической структурой, содержащей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей такой алгоритм, не составит труда, так как он выполняет одну команду за другой, и для компьютера неважно - операция ли это умножения или проверка условия.
Более того, мы можем написать громоздкий алгоритм, в котором выписаны подряд повторяющиеся действия (без использования циклической структуры). Однако с точки зрения компьютерной реализации такого алгоритма практически нет никакой разницы, использован ли в программе оператор цикла (например, 10 раз на экран выводится слово "Привет") или 10 раз последовательно выписаны операторы вывода на экран слова "Привет".
Для оценки эффективности алгоритмов введено понятие сложности алгоритма.
Определение. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.
Определение. Сложность алгоритма - количество элементарных шагов в вычислительном процессе этого алгоритма.
Обратите внимание, именно в вычислительном процессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы сложность подсчитывалась в одних и тех же элементарных действиях.
Определение. Временная сложность алгоритма - это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt.
Поскольку t зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алгоритма в первую очередь зависит от k. Очевидно, что в наибольшей степени количество операций при выполнении алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных.
Пусть есть алгоритм А. Для него существует параметр а, характеризующий объем обрабатываемых алгоритмом данных, этот параметр часто называют размерностью задачи. Обозначим через Т(n) время выполнения алгоритма, через f - некую функцию от п.
Определение. Будем говорить, что Т(n) алгоритма имеет порядок роста f(n), или, по-другому, алгоритм имеет теоретическую сложность O * (f(n)) , если найдутся такие константы с 1 , с 2 > 0 и число п 0 , что c 1 f(n)) < Т(п) < c 2 f(n) при всех п >= n 0 . Здесь предполагается, что функция f(n) неотрицательна, но крайней мере при п >= n 0 . Если для Т(п) выполняется условие Т(n) <= сf(п), то говорят, что алгоритм имеет теоретическую сложность О(п) (читается "о" большое от n).
Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность 0(п). Алгоритм сортировки методом прямого выбора имеет квадратичную сложность 0(п 2) , так как при сортировке любого массива надо выполнить (п 2 - п)/2 операций сравнения (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве, в худшем случае надо будет выполнить п перестановок). А сложность алгоритма умножения матриц (таблиц) размера п x п будет уже кубической O(n 3) , так как для вычисления каждого элемента результирующей матрицы требуется п умножений и п - 1 сложений, а всего этих элементов п 2 .
Для решения задачи могут быть разработаны алгоритмы любой сложности. Логично воспользоваться лучшим среди них, т.е. имеющим наименьшую сложность.
Наряду со сложностью важной характеристикой алгоритма является эффективность. Под эффективностью понимается выполнение следующего требования: не только весь алгоритм, но и каждый шаг его должны быть такими, чтобы исполнитель был способен выполнить их за конечное разумное время. Например, если алгоритм, выдающий прогноз погоды на ближайшие сутки, будет выполняться неделю, то такой алгоритм просто-напросто никому не нужен, даже если его сложность будет минимальной для класса подобных задач.
Если мы рассматриваем алгоритмы, реализующиеся на компьютере, то к требованию выполнения за разумное время прибавляется требование выполнения в ограниченном объеме оперативной памяти.
Известно, что во многих языках программирования нет операции возведения в степень, следовательно, такой алгоритм надо программисту писать самостоятельно. Операция возведения в степень реализуется через операции умножения; с ростом показателя степени растет количество операций умножения, которые выполняются достаточно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень.
Рассмотрим метод быстрого вычисления натуральной степени вещественного числа х. Этот метод был описан еще до нашей эры в Древней Индии.
Запишем п в двоичной системе счисления.
Заменим в этой записи каждую " 1" парой букв КХ, а каждый "О" - буквой К.
Вычеркнем крайнюю левую пару КХ.
Полученная строка, читаемая слева направо, дает правило быстрого вычисления х n , если букву К рассматривать как операцию возведения результата в квадрат, а букву X - как операцию умножения результата на х. Вначале результат равен х.
Пример 1. Возвести х в степень п = 100.
Переведем число п в двоичную систему счисления: п = 100 10 = 1100100,
Строим последовательность КХКХКККХКК
Вычеркиваем АХ слева => КХКККХКК
Вычисляем искомое значение
К => возводим х в квадрат => получаем х 2 ,
X => умножаем результат на х=> получаем х 3
К => возводим результат в квадрат => получаем х 6
К=> возводим результат в квадрат => получаем х 12 ,
К=> возводим результат в квадрат => получаем х 24 ,
Х=> умножаем результат на х =>получаем х 25
К=> возводим результат в квадрат => получаем x 50
К=> возводим результат в квадрат => получаем х 100 .
Таким образом, мы вычислили сотую степень числах всего за 8 умножений. Этот метод достаточно эффективный, так как он не требует дополнительной оперативной памяти для хранения промежуточных результатов. Однако заметим, что этот метод не всегда самый быстрый.
Например, при п = 49 учащиеся могут предложить такой эффективный алгоритм возведения в степень:
При реализации этого алгоритма было выполнено 7 операций умножения (вместо 48 операций при вычислении "в лоб") и использовано 3 ячейки (для хранения переменной х , для хранения значения х 16 и для хранения текущего результата, получаемого на каждом шаге). Если же использовать алгоритм "Быстрого возведения в степень", то получим то же количество операций (7 операций умножения), но для реализации этого алгоритма потребуется только 2 ячейки (для хранения переменной х и для хранения текущего результата).
Сама операция умножения реализуется в процессоре не "в лоб", а опять же через эффективные рекурсивные алгоритмы. Об одном из таких алгоритмов вы можете прочитать в Хрестоматии. Мы же рассмотрим алгоритм "быстрого" умножения, который был известен еще в Древнем Египте, его также называют "русским", или "крестьянским", методом. Разберем пример применения этого алгоритма.
Пример 2. Умножим 23 на 43 "русским" методом.
Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.
В итоговую сумму вошли числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа.
Похожая информация.
Также как из другими "навскидку" оценками (основанными на интуиции), суть в уже усвоенном опыте: в доступности строительных блоков, которыми вы можете оперировать бессознательно в выбранной области, благодаря целенаправленной практике.
Большинство кода имеет простую алгоритмическую структуру. И если знать оценку для распространённых блоков (алгоритмов и операций над структурами данных в вашей области), то сложность кода очевидна. В C++ сложность для стандартных алгоритмов явно указана. Знание только к какой из трёх категорий ввод относится (случайный доступ/ RandomAccessIterator, последовательный/ForwardIterator, однопроходной/InputIterator) уже достаточно во многих случаях, чтобы оценить сложность алгоритма.
Можно даже не знать как что-то конкретно реализовано. К примеру, если алгоритм на каком-то шаге требует сортировки случайных данных, то разумно предположить O(n log n) для алгоритма, основанного на сравнениях, вне зависимости от конкретной реализации. Или при поиске в таблице в базе данных, если строк много (когда о big O имеет смысл говорить), можно ожидать что добротная реализация индекс создаст (поиск из O(n) в O(log n) превращается). В случае сомнений, можно измерить .
Чтобы найти или проверить интуитивный ответ, можно рекуррентные выражения или частичные суммы построить, которые с помощью компьютера вычислить. Так как есть O(c*n) == O(n) и O(n*n + n) == O(n*n) и другие упрощающие преобразования, то многие алгоритмы можно свести к небольшому числу базовых случаев. Процесс требует внимательности, но достаточно прямолинеен (особенно если задействовать что-нибудь вроде wolframalpha, Maple, Maxima, sympy). How to find time complexity of an algorithm .
Соответственно есть случаи, когда концентрированные усилия, используя очевидные подходы, результат не дают, тогда стоит отвлечься на какое-то время, переключиться на другие задачи. Озарение может прийти в самый неожиданный момент (но это уже за рамками "навскидку").
Посмотрите какие алгоритмы используются в задачах, которые вам интересны. Новые алгоритмы с лучшей сложностью не каждый день появляются.
Начните с самого простого кода на вашем языке, framework и узнайте его сложность (к примеру, "удаление по индексу элемента из массива"). Зная сложность для элементарных конструкций, найдите сложность для блоков кода (составленных из этих конструкций), с которыми вы часто встречаетесь.
Можно в обратную сторону: начать с более высокоуровневого кода и постепенно спускаться ниже по уровням абстракции, пока до известных блоков не дойдёте (сложение фиксированных чисел, которые в машинном слове помещаются: O(1). Если произвольное число n взять, то O(log n) - пропорционально количеству бит в числе). См. таблицу сложностей по времени .
Практикуйтесь, пока большинство повседневного интересного вам кода не сможете навскидку оценить.
| Обозначение | Интуитивное объяснение | Определение |
|---|---|---|
| f ограничена сверху функцией g | src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0"> | |
| f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически | src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0"> | |
| f ограничена снизу и сверху функцией g асимптотически | 0), n_0: \forall (n>n_0) \; |Cg(n)| | |
| g доминирует над f асимптотически | src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0"> | |
| f доминирует над g асимптотически | src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0"> | |
 |
f эквивалентна g асимптотически |  |
Примеры
Замечания
Необходимо подчеркнуть, что степень роста наихудшего времени выполнения - не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:
Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.
- Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
- Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
- В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.
Классы сложности
Класс сложности - это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:
Класс P
Проблема равенства классов P и NP
Знаменитые ученые
- Леонид Левин
- Александр Разборов
- Эди Шеймир
См. также
Ссылки
- Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
- А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
- А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.
Wikimedia Foundation . 2010 .
