Вычислительная сложность: различия между версиями

=== Примеры ===

 

* '''«найти имя в телефонной книге»''' требует всего лишь время, [[логарифм]]ически зависящее от количества записей (<math>O(\log_2(n))</math>), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за <math>\log_2 1000 \approx 10</math> раз (открываний книги). При увеличении объёма страниц до ста тысяч, проблема все ещё решается за <math>\log_2 100000 \approx 17</math> заходов. (См. [[Двоичный поиск]].)