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

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

правок