Линейное время

Алгоритм с временем O(n), или линейным временем, обладает одним очень есте- ственным свойством: его время выполнения не превышает размера входных дан- ных умноженного на константу. Чтобы обеспечить линейное время выполнения, проще всего обработать входные данные за один проход, с постоянными затратами времени на обработку каждого элемента.
Другие алгоритмы достигают линейной границы времени выполнения по менее очевидным причинам. Чтобы дать пред- ставление о некоторых принципах анализа, мы рассмотрим два простых алгоритма с линейным временем выполнения.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Линейное время:

  1. ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
  2. Линейно-функциональные структуры.
  3. Время сейчас такое – время мудрости пришло!
  4. Линейный и нелинейный умы
  5. Линейный ум-эго
  6. Линейные структуры.
  7. Модификации линейной организационной структуры.
  8. Линейное и нелинейное мышление
  9. Линейное и нелинейное мышление
  10. Линейный и нелинейный ум
  11. Линейный и нелинейный умы
  12. 14. 4. Рабочее время и время отдыха
  13. Зарубка на носу Дай время себе, дай время ребенку
  14. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  15. Время