Оценка сложности алгоритмов
Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.
Память или время
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.
Оценка порядка
При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
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! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.
Оценка сложности алгоритмов, или Что такое О(log n)
Если вы всё ещё не понимаете, что такое вычислительная сложность алгоритмов, и ждете простое и понятное объяснение, — эта статья для вас.
Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.
Оценка сложности
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.
Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n3) , т. е. зависит от размера входных данных кубически.
Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .
Примеры
O(n) — линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
O(log n) — логарифмическая сложность
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
O(n2) — квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n2 .
Бывают и другие оценки по сложности, но все они основаны на том же принципе.
Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.
Наглядно
Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 106 операций в секунду:
Если хочется подробнее и сложнее, заглядывайте в нашу статью из серии «Алгоритмы и структуры данных для начинающих».
Емкостная сложность алгоритмов
Объясните пожалуйста, на простом примере, как вычислять емкостную сложность алгоритмов.
Буду благодарен, спасибо.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public CountSort(int size) { thearray = new int [size] ; Random ran = new Random(); for(int i = 0 ; i size; i++) { thearray[i] = ran.Next(7, 23); } }
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Сложность алгоритмов
Оценить временную сложность алгоритма выбора лучшего хода в русских шашках.
Временная сложность алгоритмов
Сколько времени займет подсчет до 1 миллиарда (не учитывая переполнение)? Определите время работы.
Временная сложность алгоритмов
Здравствуйте! Собственно, задание: даны 2 алгоритма, надо узнать что они выполняют и их временную.
Сложность алгоритмов + паралельные вычисления
Здравствуйте. Возник вопрос касательно сложности алгоритмов. Допустим у нас есть алгоритм.
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
емкостная сложность — это функция, выражающая зависимость требуемой памяти от размера входных данных.
например, вам дан массив и требуется вывести его в отсортированном порядке. если вам дадут сто чисел, то вам понадобится массив из 100 ячеек. если миллион чисел — массив из миллиона ячеек. зависимость необходимой памяти от размера входных данных линейная. поэтому скажем, что емкостная сложность алгоритма, решающего задачу сортировки .
другая задача. надо найти наибольшую общую подстроку двух строк. предположим, вы умеете решать ее только динамикой и ко всему прочему вы еще и не умеете оптимизировать по памяти эту динамику тогда вы будете насчитывать матрицу dp[длина первой строки][длина второй строки]. ну тогда, если обе строки длиной 10, то вам потребуется матрица из 100 ячеек. а если длины 100, то матрица из 10000 ячеек. зависимость уже квадратичная. тогда сложность оценим как .
ну вот в таком роде.
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Сложность алгоритмов
Добрый день, пытаюсь оценить сложность алгоритмов, но возникли сомнения в правильности рассчетов.
Оценить сложность алгоритмов
Добрый день. Мне нужно оценить сложность алгоритмов. Я это сделал, но сделал с ошибками. Могли бы.
Или воспользуйтесь поиском по форуму:
Как определить емкостную сложность алгоритма
На этом шаге мы рассмотрим понятие о сложности алгоритма .
Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой и с незначительными вариациями в архитектуре.
Такой подход сложился исторически и ориентируется прежде всего на научные и инженерные приложения теории алгоритмов: объемы данных значительно превышают размеры самой программы, а программа может выполняться несколько часов. Если не считать офисных и бухгалтерских применений вычислительных машин, то производительность и объем памяти компьютера никогда не казались программистам чрезмерными и постоянной задачей является сделать программу работающей хотя бы немного быстрее и попытаться заставить ее работать в стесненных условиях ограниченного поля памяти.
Если в научных и инженерных приложениях большое время вычислений доставляет лишь неудобство пользователям, то в ряде других областей ресурсы настолько критичны, что может возникнуть проблема целесообразности всего проекта из-за неэффективной работы программы. К таким областям относятся системы реального времени ( real-time systems ). Это основанные на компьютерах системы, которые управляют процессами в реальном мире или обрабатывают информацию, служащую для принятия оперативных решений. Примерами систем реального времени являются бортовые компьютерные системы космических кораблей, самолетов, других транспортных средств; компьютерные системы, управляющие непрерывным химическим производством, ядерными реакторами; системы противовоздушной обороны, управления огнем и др.
В данном разделе будут рассмотрены две характеристики сложности алгоритмов — временная и емкостная . Не будем обсуждать сложность (длину) текста алгоритма, поскольку она больше характеризует исполнителя (машину), его язык, а не метод решения задачи. Не будем также обсуждать логическую сложность разработки алгоритма — сколько человеко-месяцев нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики. Обе эти темы относятся к области компьютерных наук, называемой «технология программирования» ( software engineering ).
Единицы измерения сложности будем привязывать к классу архитектур наиболее распространенных ЭВМ. Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством скалярных переменных, элементов массивов, элементов записей или просто количеством байт.
Одно из свойств алгоритма — массовость . В общем случае количество операций и требуемая память зависят от исходных данных, т.е. являются функциями вектора X = (х 1 , х 2 , . х n ) исходных данных. С точки зрения математического анализа сложности, сравнения алгоритмов, их классификации хотелось бы, чтобы функции сложности (x 1 , x 2 , . x n ) выражались в виде формул с использованием обычных, элементарных математических функций. Тогда в нашем распоряжении оказался бы богатый арсенал средств классической математики. Но это не всегда возможно, так как исходные данные могут быть нечисловыми (графы, географические карты, строки символов, звуки и т. д.). Поэтому сложность алгоритма a рассматривается как функция от некоторого интегрированного числового параметра V , характеризующего исходные данные. Обозначим: Tα(V) — временная сложность алгоритма α ; Sα(V) — емкостная сложность.
Параметр V , характеризующий данные, называют иногда объемом данных или сложностью данных . Оба эти термина не совсем точны. Выбор параметра V зависит не только от вида данных, но и от вида алгоритма или от задачи, которую этот алгоритм решает.
Задача вычисления факториала числа x ( x>0 ). Программа итеративного решения задачи имеет следующий вид:
function Factorial (х: integer): integer; var m, i: integer; begin m := 1; for i := 2 to x do m := m*i; Factorial := m; end;
Количество операций здесь подсчитывается легко: один раз выполняется оператор m := 1 ; тело цикла (умножение и присваивание) выполняется (х-1) раз; один раз выполняется присваивание Factorial := m . Если сложность каждой из элементарных операций считать равной единице, то временная сложность приведенного алгоритма будет равна 1+2(x-1)+1=2х . Из этого анализа ясно, что за параметр V удобно принять значение х .
Эти два примера иллюстрируют ситуации, когда для оценки сложности важны значения исходных данных (1) и количество исходных данных (2). Первая ситуация является более общей, так как k во втором примере фактически тоже входит в перечень исходных данных. Однако второй пример показывает, что от некоторых исходных данных сложность алгоритма может не зависеть. Собственно говоря, для анализа сложности не всегда можно сформулировать интегральный параметр V и лишь после построения оценки становится ясно, какая характеристика исходных данных является значимой для данного алгоритма.
Отыскание функций сложности алгоритмов важно как с прикладной, так и с теоретической точек зрения.
В практике проектирования систем реального времени задача разработки программы формулируется так: отыскать такой алгоритм a , решающий задачу P , что Тα(X) < Tmax при X ∈ D , где D - область допустимых значений входных данных (задача с ограничением на временную сложность).
В системах, где критерий качества связан с временем ожидания реакции компьютера (системы управления базами данных, системы автоматического перевода для естественных языков программы для игры в шахматы и другие) задача может быть поставлена так: отыскать среди всех алгоритмов, решающих задачу Р , такой алгоритм а , для которого функция Tα(X) будет принимать минимальные значения на выбранном подмножестве S значений исходных данных, X ∈ S ⊂ D (задача минимизации временной сложности; дополнительно формулируются ограничения по емкостной сложности).
Двойственная задача минимизации емкостной сложности при ограничениях на временную сложность возникает реже в силу архитектурных особенностей современных ЭВМ. Дело в том, что запоминающие устройства разных уровней, входящие в состав машины, построены так, что программе может быть доступна очень большая, практически неограниченная область памяти — виртуальная память. Недостаточное количество основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Если учесть, что в любой момент времени программа работает лишь с двумя-тремя значениями и использование кэша и аппаратного просмотра команд программы вперед позволяет заблаговременно перенести с диска в основную память нужные значения, то можно констатировать, что минимизация емкостной сложности не является первоочередной задачей. Поэтому в дальнейшем будем интересоваться в основном временной сложностью алгоритмов.
С теоретической точки зрения важным является вопрос: как далеко для данной задачи можно продвигаться по пути совершенствования (уменьшения сложности) алгоритмов ее решения, когда наступает предел, свойственный самой задаче, далее которого попытки совершенствования алгоритмов заведомо не приведут к успеху?
Другой интересный вопрос связан с классификацией алгоритмов. Числовая функция Tα(V) растет (обычно) с возрастанием значений аргумента V . Как быстро она растет? Существуют алгоритмы с линейной зависимостью временной сложности от объема данных, со сложностью, возрастающей пропорционально квадрату V , более высоким степеням V . Такие алгоритмы называются полиномиальными . А существуют алгоритмы, сложность которых увеличивается быстрее любого полинома. Ясно, что с точки зрения возможностей реализации они значительно отличаются друг от друга. Поэтому очень много исследований посвящено вопросам типа «возможен ли для данной задачи полиномиальный алгоритм»?
На следующем шаге мы рассмотрим верхние и средние оценки сложности алгоритмов .