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

м
м (Удаление принудительных пробелов в формулах по ВП:РДБ.)
Метка: правка из мобильного приложения
 
=== Примеры ===
* '''«почистить ковёр пылесосом»''' требует время, линейно зависящее от его площади (<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> заходов. (См. [[Двоичный поиск]].)
 
=== Замечания ===