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

Как оценить насколько быстрая написанная нами программа? Как оценить скорость программы?

Измерить временной шкалой? Минуты, секунды и милисекунды? Но в таком случае одна и та же программа на разных компьютерах будет показывать разные результаты.

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

Представим сложность алгоритма как некую зависимость от количества входных данных - 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=bне что иное как y=logba | => x*logba

Теперь давайте представим a= z, тогда x = logaz

Тогда предыдущее уравнение будет выглядеть так:

logbz = logaz*logba  => logbz = logaz*C, где С константа

Это правило говорит, что от логарифма от одного основания можно перейти к логарифму с другим основанием домножив на какое-то число.

Это значит, что при оценке нам не важно по какому основанию сложность алгоритма, потому-что мы можем привести к любому основанию домножив на константу. Поэтому при оценке мы пишем просто logn и не пишем по какому основанию, потому-что не важно по какому основанию.

Например, алгоритм сложения в столбик 2-х чисел x, y:

Количество цифр в числе равно log (число), получается сложность такого алгоритма: log(max(x,y))

 

Представим что у нас есть алгоритмы разной сложности

n*log2n

Увеличим входные данные в 4 раза и посмотрим, что будет


n = n*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

 

комментарии (1)

vladimir vladimir 2018-05-26 09:55:53
Не самая плохая статья, спасибо. Особенно ссылки понравились :)