Перед тем как переходить к самим алгоритмам, нам нужно разобраться с базовой терминологией.
И так, самое первое, что нужно разобрать - это, собственно, само определение алгоритмов.
Алгоритм - это непосредственно инструкция с последовательностью действий для выполнения той или иной задачи. К примеру, "алгоритм решения простых уравнений". Предположим, что у нас есть простое уравнение:
3x + 15 = 0
Алгоритм его решения будет следующим:
- Раскрываем скобки (их нет).
- Оставляем значения с переменными в левой части, а остальные переносим в правую.
- Избавляемся от коэффициента для x, т.е. делим обе части на этот коэффициент.
- Получаем результат. x = -5
Следующее, что хотелось бы обсудить - это "сложность" алгоритма. Эта оценка показывает, какое максимальное количество шагов необходимо совершить, чтобы достичь результата, в зависимости от количества входных данных. Обозначается как Big O, О-большое или просто O(...).
В реальной практике зачастую используется последний способ написания, O(...). Но что же должно быть в скобках? В скобках записывается функция, какая-то операция над размером входных данных, которая показывает верхнюю границу роста времени выполнения.
Чтобы вышеописанное стало более понятным, рассмотрим самые популярные нотации с примерами:
- O(1) - константная (постоянная) сложность. Означает, что вне зависимости от размера данных количество шагов не будет изменяться. И действительно, если мы вернёмся к примеру с нашим уравнением, то, как бы мы его ни видоизменяли, количество операций для решения будет постоянным.
- O(log n) - логарифмическая сложность. Сложность выполнения алгоритма растёт медленнее, чем количество данных. Т.е., если у нас есть 100 элементов, то алгоритм данной сложности потребует максимум 7 шагов. К этой сложности относится алгоритм бинарного поиска.
- O(n) - линейная сложность. Сложность выполнения алгоритма растёт аналогично увеличению числа входных данных. К примеру, просмотр всех документов в папке.
- O(n^2) - квадратичная сложность. Сложность выполнения алгоритма растёт пропорционально квадрату количества элементов. К примеру, если внутри цикла (O(n)) у нас есть ещё один вложенный цикл. Или сортировка пузырьком.
- O(2^n) - экспоненциальная сложность. Чаще всего встречается при неоптимизированной рекурсии.
- O(n * log n) - линейно-логарифмическая сложность. Сложность алгоритма растёт быстрее, чем при линейной сложности, но медленнее, чем при квадратичной. В качестве примера приводят merge sort, но с этим алгоритмом я лично не сталкивался. Обязательно рассмотрим в дальнейших статьях.
- O(n^x) - степенная сложность. Это алгоритмы, которые зачастую имеют x вложенных циклов.
- O(n!) - факториальная сложность. Это самая высокая сложность алгоритмов, поскольку она пропорциональна факториалу (произведению всех целых чисел) числа n. Т.е., если у нас 10 элементов, то для выполнения потребуется 1*2*3*4*5*6*7*8*9*10 = 3628800 шагов. Такой алгоритм встречается при подсчёте всех возможных комбинаций.
Заключение
Мы разобрались с основной метрикой оценки сложности алгоритмов, поговорили о самых популярных функциях. В следующих статьях мы рассмотрим алгоритмы, которые используют эти оценки.
Это ещё не все обозначения сложности алгоритмов, но на текущем этапе остановимся именно на них, поскольку эти оценки самые распространённые. Если вам интересно, можете более подробно прочитать о других обозначениях в замечательной статье на Хабре: https://habr.com/ru/articles/782608/
Telegram-канал: https://t.me/pyhub_ai
