Оценка сложности алгоритмов
Как оценить насколько быстрая написанная нами программа? Как оценить скорость программы?
Измерить временной шкалой? Минуты, секунды и милисекунды? Но в таком случае одна и та же программа на разных компьютерах будет показывать разные результаты.
Мы можем считать количество операций. И тогда наши показатели не будут зависеть от машины, где запускается программа.
Представим сложность алгоритма как некую зависимость от количества входных данных - n. Тогда мы можем записать примерные виды сложности алгоритмов:
534*n3 + 16*n2 + 256
2n4 + 10
Какой из этих алгоритмов быстрее работает?
Для оценки мы берем только наихудщие случаи с точностью до коэффициента. Представим что n стремится к большому числу. В таком случает понятно, что константы не играют болшой роли. И в практике оценки алгоритма принято брать только худшие слагаемые. Худшие имеются ввиду те, что быстрее всех растет. Если входные данные небольшие, то они быстро работают при любых алгоритмах и нет необходимости. Таким образом мы приходим к таким упрощениям:
n3
n4
Видно, что второй алгоритм дольше работает чем первый. Конечно, это все теоретически. В теории мы берем максимально большие числа. А на практике нужно исходить от тех исходных данных которые есть или которые могут быть.
Сравним несколько алгоритмов:
Сложность алгоритма, где n это развер входных данных | Во столько раз замедлится скорость при увеличении входных данных в 10 раз |
n | 10 |
n2 | 100 |
n3 | 1000 |
2n | 210 |
Можно выделить по этой таблице 2 типа:
nk, где k константа, говорят, что они работают за полином или за полиномиальное время работы. Имеют такое свойство: если увеличим входные данные во сколько то раз, то время работы увеличится во сколько-то раз.
kn, где k константа, говорят работает за экспоненциальное время работы.
Неможножко о логарифме...
Количество цифр в числе - это грубая оценка для величины, которая называется логарифм числа.
15 (2 цифры) - log1015 = 1,...
235 (3 цифры) - log10235 = 2,...
1000000 (7 цифр) - log10(106) = 6
С логарифмами связаны некоторые правила:
logaax = x
loga1 = 0
loga(x*y) = logax + logay
И последнее:
logbax => | представим a=by | => logb(by)x = logbbxy = xy => | a=by не что иное как y=logba | => x*logba
Теперь давайте представим ax = z, тогда x = logaz
Тогда предыдущее уравнение будет выглядеть так:
logbz = logaz*logba => logbz = logaz*C, где С константа
Это правило говорит, что от логарифма от одного основания можно перейти к логарифму с другим основанием домножив на какое-то число.
Это значит, что при оценке нам не важно по какому основанию сложность алгоритма, потому-что мы можем привести к любому основанию домножив на константу. Поэтому при оценке мы пишем просто logn и не пишем по какому основанию, потому-что не важно по какому основанию.
Например, алгоритм сложения в столбик 2-х чисел x, y:
Количество цифр в числе равно log (число), получается сложность такого алгоритма: log(max(x,y))
Представим что у нас есть алгоритмы разной сложности
n*log2n |
Увеличим входные данные в 4 раза и посмотрим, что будет
|
n*log2(n*4) = n*log2n + n*log24 => выросло на 2 |
n2 | (n*4)2= n2*42 => выросло в 16 раз | |
n√n | n√(n*4) = n√n * 2 => выросло в 2 раза |
Логарифм работает быстрее даже если мы будем сравнивать с алгоритмом, который работает со сложностью n в степени 1/10^6, т.е n1/10^6
Если мы входные данные увеличим в 2 в степени миллион (210^6), то у нас получится, что логарифм растет на миллион, когда сравниваемый с ним n1/10^6 растет в 2 раза.
И с какого-то момента, в данном случае с 10^6 логарифм все таки начнет работать быстрее.
n100 - на практике большое число даже при n=2, и до таких чисел обычно не добираются, но теоретически алгоритм с такой сложностью быстрее работает.
2n - на практике этот алгоритм быстрее
Посмотрим на примере алгоритм пузырьковой сортировки.
for j:=1 to n do:
for i:=1 to n-1 do:
if (a[i] > a[i+1]) then
a[i] меняем местами a[i+1];
Мы видим, что сложность алгоритма у нас n^2
Улучшим наш алгоритм, понимая, что после первого прохода самое большое число становится на свое место и нам не нужно каждый раз проходиться до конца. Тогда наш алгоритм будет вылгядеть следующим образом
for j:=1 to n do:
for i:=1 to n-j do:
if (a[i] > a[i+1]) then
a[i] меняем местами a[i+1];
Сложность этого алгоритма примерно 1/2n^2. Но нам коэффициент не важен поэтому у нас сложность будет также n^2.
Типичные примеры "О-большого"
O(log n) или логарифмическое время - Бинарный поиск
O(n) или линейное время - простой поиск с прохождением всех значений
O(n*log n) - эффективные алгоритмы сортировки (быстрая сортировка)
O(n2) - медленные алгоритмы сортировки (сортировка выбором)
O(n!) или факториальное время - очень медленные алгоритмы (задача о коммивояжере)
Ссылки:
https://habrahabr.ru/post/104219/
https://habrahabr.ru/post/188010/
https://tproger.ru/articles/computational-complexity-explained/
https://pro-prof.com/archives/1660
https://www.youtube.com/watch?v=ZRdOb4yR0kk