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

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