Для чего же нам может потребоваться умение определять сложность алгоритмов?
Рассмотрим абстрактный пример.
Предположим у нас есть задача, передать листок бумаги с информацией на расстояние X. Что бы выполнить задание можно воспользоваться одним из трёх инструментов: отвезти листок на машине, отправить его на самолёте, и приклеить к панцирю черепахи(животное в примере, является крайне мотивированным и ползёт всегда в нужном направление, от клея на панцире не страдает). Существуют две дистанции на которые требуется передать данные:
- 3 сантиметра
- 1000 километров
А победители на дистанциях определенно ясны, на 3 сантиметрах - это черепаха так как жигули не успеют завестись, а СУ-27 прогреть двигатели для начала движения, в то время как черепахе потребуются считанные секунды, но на 1000 километрах наиболее выгоден безоговорочно будет самолёт, который покажет многократное преимущество над авто и черепахой.
Теперь проведём ряд параллелей с алгоритмами и их сложностью, алгоритмы в примере, как не сложно догадаться - черепаха, машина и самолет, сложность алгоритмов(вычислительная сложность, O-нотация, Θ - нотация) - скорость передвижения которую способны развивать наши инструмент передачи листка, расстояние же можно сравнить с количеством операций исполняемых процессором в совокупности с количеством входных данных, а умение определять сложность алгоритма и верно подобрать его под определенную задачу, равносильно умению(опыту) с помощью которого мы можем примерно определить скорость наших средств доставки и предсказать что выгоднее и на какой дистанции.
Кроме выше перечисленных пунктов почему стоит уметь определять сложность алгоритма существуют такие важные нюансы как:
Уменьшение сложности алгоритма путём его модернизации как правило заметно сильнее увеличивает производительность программы чем замена языка программирования.
После определения сложности можно предсказать поведение и возможность применения алгоритма на других объемах входных данных.
Простейший подсчет команд
Небольшой фрагмент кода на языке С шарш.
Разберём команды
в сортировке используется два цикла, при том один как всем известно вложен в другой при это первом выполняется n-1 (длина массива), во втором, вложенном цикле (n-1)/2 в два раза меньше чем в первом
Общее число шагов алгоритма равно данному квадратному уравнению, далее при оценке сложности алгоритма важно знать, что:
- Константы при оценке не учитываются, поэтому алгоритм описываемый O(3n+2) должен быть записан O(n).
- Не важная сложность выражения отбрасываются O(2n^2+3n) = O(n^2).
Константы это?
Постоянные величины значение которых не изменяются, коэффициенты при n тоже являются константами.
Как определить не важную сложность, что это такое?
Разберёмся на примере O(n^2+n), n будет иметь не важную сложность по сравнению n^2, так как n^2 значительно больше n при условии, что в расчёт мы не берём n=0,1,2 (сложность рассчитывается на бесконечно больших n)
Значительно больше - это больше чем в два раза.
В случае возникновения сомнений, что же всё таки больше, можно прибегнуть к помощи поисковика.
По графикам легко определить не важную сложность, график быстрее растущий по оси Y и является показателем наиболее важного слагаемого.
Во время записи слагаемых в поисковик стоит заменить n на x, а так же приравнять и представить их в виде функций, и что важно между функциями требуется писать запитую.
Когда стоит складывать, а когда умножать?
Умножать стоит когда циклы вложены друг в друга, это не обязательно могут быть FOR, как приведено в примере с пузырьковой сортировкой, так же можно умножать и на количество операций, в самом цикле таких как например присваивание, но этого можно не делать так как данные действия приводят к появлению констант, от чего мы по итогу избавляемся.
Сложение применяется как это не странно при последовательно расположение команд.
Сложность функции diffEven равна O(n+n) = O(2n) = O(n).
Но нельзя забывать, что если у нас есть несколько аргументов в функции, то прибегать к окончательному сложению или умножению не стоит, сложность так и будет записана O(n+m^2), O(k*m*n).
O-нотация, Θ-нотация, ω-нотация
У всех выше приведённых понятий есть общее,что они представляют из себя математические обозначения используемые для описания и сравнения асимптотического поведения функций, а непосредственно в теме сложности алгоритмов нотации показывают зависимость между количеством операций выполненных процессором и объемом входных данных.
Но есть и отличия.
O - большое описывает верхнюю границу сложности (сложнее неё алгоритм быть не может).
ω - нижнюю границу сложности.
Θ - совокупность O и ω наиболее точная оценка сложности.
Заключение
В целом, тема определения сложности алгоритма обширна, если в неё продолжить углубляться можно узнать какие алгоритмы всегда дают log n, открыть для себя, что сложность подвергается рассмотрению с таких сторон как наилучший, наихудший случай или же ожидая сложность.
Спасибо за прочтение статьи.