На этом шаге рассмотрим понятие "О-большое".
Специальная нотация "О-большое" описывает скорость работы алгоритма. Время от времени нам придется использовать чужие алгоритмы, а потому неплохо было бы понимать, насколько быстро или медленно они работают.
Предположим, имеется список размера n. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить n операций. Бремя выполнения "О-большое" имеет вид О(n). Для проверки списка размером n бинарному поиску потребуется log n операций.
"О-большое" позволяет сравнить количество операций, указывает, насколько быстро возрастает время выполнения алгоритма.
Предположим, вы используете простой поиск для угадывания числа от 1 доя 100. Мы знаем, что простой поиск выполняется за время О(n), то есть в худшем случае нам придется называть каждое число. Но представим, что загодано число 1. В общем, нам не пришлось перебирать все числа - мы угадали с первой попытки. Отработал ли алгоритм за время О(n)? А может, он занял время О(1), потому что результат был получен с первой попытки?
Простой поиск все равно выполняется за время О(n). Просто в данном случае мы нашли нужное значение моментально; это лучший возможный случай. Однако "О-большое" описывает худший возможный случай. Фактически в худшем случае придется перебрать все числа. Это и есть время О(n). И это гарантирует, что простой поиск никогда не будет работать медленнее О(n).
На следующем шаге рассмотрим примеры "О-большого".
