Расскажем просто и понятно, как определить временную и пространственную сложность алгоритмов — и зачем нужно это делать. Что такое «О» большое «О» большое (Big O notation) — это математическая нотация, которая позволяет оценить, как изменяется время выполнения алгоритма или объем используемой памяти в зависимости от размера входных данных. Есть еще «о» малое — эта нотация дает более строгую верхнюю границу для сложности алгоритма, но часто ее труднее вычислить, чем «О» большое. На практике «О» большое...

Какие бывают нотации ? Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа: O(g(n)) – Big O – определяет верхнюю границу для работы алгоритма (свободная верхняя граница). Функция описывает зависимость между входными параметрами и кол-вом операций которые придется выполнить. Ω(g(n))– Big Ω(Omega) используется для описания по нижней границе работы алгоритма. (свободная нижняя граница) Θ(g(n)) - Big-Θ (Theta) – используется для определения как верхней так и нижней...