1 ГЛАВА '«О-большое» определяет время выполнения в худшем случае'
Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время О(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте , что искомая фамилия начинается на букву 'А' и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи - вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время О(n)? А может, он занял время О(1), потому что результат был получен с первой попытки?
Простой поиск все равно выполняется за время О(n) . Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако 'О-большое' описывает худший возможный случай . Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время О(n). И это дает определенные гарантии - вы знаете, что простой поиск никогда не будет работать медленнее О(n).
ПРИМЕЧАНИЕ
Наряду с временем худшего случая также полезно учитывать среднее время выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.