Сложность алгоритмов
Вы наверное встречали такие обозначения, как O(n) или O(log n). Так что же они обозначают? Давайте разбираться! Big O Данное понятие довольно распространено в мире алгоритмов и обозначает время выполнения программы, а также количество памяти, которую она использует. Ω (Омега) Следующее понятие является полной противоположностью предыдущего и обозначает минимальное время выполнения алгоритма. Примеры Сложность каждого алгоритма зависит от количества операций и определяется по формуле, записанной в виде O(<формула>). O(n) - Линейный поиск В данном примере количество операций определяется положением элемента в контейнере, и в худшем случае искомый элемент может находиться в конце контейнера...
1225 читали · 3 года назад
Оценка сложности алгоритмов Big O
Какие бывают нотации ? Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа: O(g(n)) – Big O – определяет верхнюю границу для работы алгоритма (свободная верхняя граница). Функция описывает зависимость между входными параметрами и кол-вом операций которые придется выполнить. Ω(g(n))– Big Ω(Omega) используется для описания по нижней границе работы алгоритма. (свободная нижняя граница) Θ(g(n)) - Big-Θ (Theta) – используется для определения как верхней так и нижней...