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

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

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

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

Представим сложность алгоритма как некую зависимость от количества входных данных - n. Тогда мы можем записать примерные виды сложности алгоритмов:

534*n³ + 16*n² + 256

2n⁴ + 10

Какой из этих алгоритмов быстрее работает?

Для оценки мы берем только наихудщие случаи с точностью до коэффициента. Представим что n стремится к большому числу. В таком случает понятно, что константы не играют болшой роли. И в практике оценки алгоритма принято брать только худшие слагаемые. Худшие имеются ввиду те, что быстрее всех растет. Если входные данные небольшие, то они быстро работают при любых алгоритмах и нет необходимости. Таким образом мы приходим к таким упрощениям:

n³

n⁴

 Видно, что второй алгоритм дольше работает чем первый. Конечно, это все теоретически. В теории мы берем максимально большие числа. А на практике нужно исходить от тех исходных данных которые есть или которые могут быть.

Сравним несколько алгоритмов:

Можно выделить по этой таблице 2 типа:

n^k, где k константа, говорят, что они работают за полином или за полиномиальное время работы. Имеют такое свойство: если увеличим входные данные во сколько то раз, то время работы увеличится во сколько-то раз.

kⁿ, где k константа, говорят работает за экспоненциальное время работы. 

Неможножко о логарифме...

 Количество цифр в числе - это грубая оценка для величины, которая называется логарифм числа.

15 (2 цифры) - log₁₀15 = 1,...

235 (3 цифры) - log₁₀235 = 2,...

1000000 (7 цифр) - log₁₀(10⁶) = 6

С логарифмами связаны некоторые правила:

log_aa^x = x

log_a1 = 0

log_a(x*y) = log_ax + log_ay

И последнее:

log_ba^x => | представим a=b^y | => log_b(b^y)^x = log_bb^xy = xy => | a=b^y не что иное как y=log_ba | => x*log_ba

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

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

log_bz = log_az*log_ba  => log_bz = log_az*C, где С константа

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

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

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

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

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

Логарифм работает быстрее даже если мы будем сравнивать с алгоритмом, который работает со сложностью n в степени 1/10^6, т.е n^{1/10^6}

Если мы входные данные увеличим в 2 в степени миллион (2^{10^6}), то у нас получится, что логарифм растет на миллион, когда сравниваемый с ним n^{1/10^6} растет в 2 раза. 

И с какого-то момента, в данном случае с 10^6 логарифм все таки начнет работать быстрее.

n¹⁰⁰ - на практике большое число даже при n=2, и до таких чисел обычно не добираются, но теоретически алгоритм с такой сложностью быстрее работает.

2ⁿ - на практике этот алгоритм быстрее 

Посмотрим на примере алгоритм пузырьковой сортировки.

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(n²)  - медленные алгоритмы сортировки (сортировка выбором)

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