Big O Notation: Информация для общего развития
Стоит отметить, что Big O Notation рассматривает худший случай.
Например: Дан массив. Известно, что в нем все числа нечетные кроме одного. Начинаем перебор массива. Худший случай - нахождение четного числа на последней позиции. Именно поэтому в понимании Big O Notation сложность будет O(n).
___
Немного информации для общего развития 🍔
На собеседованиях это не понадобится...
Ω (омега)
Ω (омега) - показывает лучший случай, т.е. насколько быстро алгоритм может отработать при самых благоприятных входных данных.
В примере выше лучший случай - нахождение четного числа на первой позиции. Начинаем перебор и сразу находим искомый результат.
То есть, для этой задачи:
- O(n)
- Ω(1)
___
Также существует Θ (тета) - точная асимптотика.
O и Ω могут совпадают.
Например: Необходимо просуммировать все элементы массива. В любом случае нам придется перебирать все элементы и складывать их. Сложность: O(n) и Ω(n)
___
course_intro
