Вы наверное встречали такие обозначения, как O(n) или O(log n). Так что же они обозначают? Давайте разбираться!
Big O
Данное понятие довольно распространено в мире алгоритмов и обозначает время выполнения программы, а также количество памяти, которую она использует.
Ω (Омега)
Следующее понятие является полной противоположностью предыдущего и обозначает минимальное время выполнения алгоритма.
Примеры
Сложность каждого алгоритма зависит от количества операций и определяется по формуле, записанной в виде O(<формула>).
O(n) - Линейный поиск
В данном примере количество операций определяется положением элемента в контейнере, и в худшем случае искомый элемент может находиться в конце контейнера.
O(log n) - Бинарный поиск
Выполняет ту же самую функцию, что и линейный поиск, только делает это быстрее для случаев, когда элемент находится не в начале, а в конце или середине контейнера. Суть данного алгоритма расписана здесь.
O(n^2) - Обход 2D контейнера
Данный пример обычно характеризуется наличием вложенного цикла.
O(n * log n) - Сортировка слиянием
Значит, что увеличение размера контейнера влечет за собой увеличение количества операций в 1-2 раза. По сути, это улучшенная версия O(n^2) и является смесью O(log n) и O(n). Подробно ознакомиться с, приведенным в качестве примера, алгоритмом можно здесь.
Заключение
Надеюсь, данная статья была полезной, и вы чуть больше узнали об алгоритмах!