Какие бывают нотации ?
Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа:
O(g(n)) – Big O – определяет верхнюю границу для работы алгоритма (свободная верхняя граница). Функция описывает зависимость между входными параметрами и кол-вом операций которые придется выполнить.
Ω(g(n))– Big Ω(Omega) используется для описания по нижней границе работы алгоритма. (свободная нижняя граница)
Θ(g(n)) - Big-Θ (Theta) – используется для определения как верхней так и нижней границы работы алгоритма (строгая верхняя и нижняя границы)
Для чего нужна нотация BIG O
Big O нотация нужна для описания сложности алгоритмов. Тут важно понимать, что мы оцениваем время выполнения лишь косвенно, потому что на разном окружение один и тот же код может выполняться разное время. Понимание этой нотации нужно чтобы научиться видеть и исправлять не оптимальный код.
«O» большое и «o» малое — математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.
Асимптотическая сложность алгоритмов представляет собой время и память, которые понадобятся вашей программе в процессе выполнения.
Основные допущения
Для оценки в качестве N используется бесконечность
Все константы не влияющие на «бесконечность» будут отброшены. Например, алгоритмы описываемые как O(2*N) и O(N+100) и даже O(N + logN) - это все равно O(N).
При этом если алгоритм имеет несколько неизвестных влияющих на сложность например, O(N+M) – M мы не можем отбросить, потому, что мы о нем ничего не знаем и оно может быть так же равно бесконечности (быть больше N).
Основные классы сложности применяемые при анализе
f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост
Как видно из графика все что больше O(n log n)уже имеет довольно сильный рост сложности и мало эффективны
Оценка O(1)
Применяется когда можно узнать результат за одно действие. Например, найти значение массива по ключу.
O(log(n)) логарифмический рост
Этот случай подходит для оценки алгоритмов с определенными допущениями. Например, бинарный алгоритм поиска (Binary search). Для его работы входной массив данных уже должен быть отсортирован. Тогда на каждой итерации мы будем искать лишь в половине элементов от предыдущего шага. Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).
O(n) линейный рост
Давайте представим ситуацию когда чтобы узнать результат нам нужно пройти по всем элементам массива (дерева). Тогда такой алгоритм и будет иметь сложность O(n). Например сложение всех элементов массива.
Так же если мы вызываем функцию рекурсивно и она делает простую операцию, то сложность будет так же O(n)
O(n*log(n)) квазилинейный рост
Хорошим примером такого алгоритма является Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за O(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)). С подробностями стоит ознакомиться самостоятельно, т.к. сам алгортм заслуживает отдельной статьи.
O(2^n) экспоненциальный рост
Тут будут лишь примеры задач, т.к. с такой сложностью решения как правило не тривиальны.
с^n - Нахождение (точного) решения задачи коммивояжера с использованием динамического программирования; определение, если два логических утверждения эквивалентны, используя грубую силу
O (n!) - решение проблемы коммивояжера с помощью перебора
Когда сложение? а когда умножение ?
Сложение, в оценке сложности используется, когда в алгортме присутствует последовательность действий друг за другом O(N+M)
Умножение, в оценке сложности используется, когда в алгортме присутствует выполнение какого-то действия в связке с выполнением другого. Например, цикл в цикле. O(N*M)
Это лишь базовые знания по оценки сложности алгоритмов, но они могут помочь Вам разобраться в этом не лёгком деле.