Обзор типичных вариантов времени выполнения

Когда вы пытаетесь проанализировать новый алгоритм, полезно иметь хотя бы приблизительное представление о «спектре» разных вариантов времени вы- полнения. В самом деле, некоторые типы анализа встречаются часто, и когда вы сталкиваетесь с распространенными границами времени выполнения вида 0(n), 0(n log n) или 0(n2), часто это объясняется одной из немногочисленных, но хорошо узнаваемых причин.
Для начала мы приведем сводку типичных границ времени выполнения, а также типичные аналитические методы, приводящие к ним.

Ранее мы уже говорили о том, что у многих задач существует естественное «пространство поиска» — совокупность всех возможных решений, а также упо- минали, что объединяющей темой в проектировании алгоритмов является поиск алгоритмов, превосходящих по эффективности перебор пространства поиска ме- тодом «грубой силы». Соответственно, когда вы беретесь за новую задачу, часто бывает полезно рассматривать два вида границ: для времени выполнения, кото- рое вы рассчитываете достичь, и для размера естественного пространства поиска задачи (а следовательно, для времени выполнения алгоритма методом «грубой силы»). Обсуждение вариантов времени выполнения в этом разделе часто будет начинаться с анализа алгоритма «грубой силы», который поможет разобраться в особенностях задачи. Большая часть книги будет посвящена тому, как добиться повышения быстродействия по сравнению с такими алгоритмами.

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

Еще по теме Обзор типичных вариантов времени выполнения:

  1. Управление временем «Нам некогда делать это как следует - у нас хватает времени лишь на то, чтобы потом все переделывать».
  2. ПОРТРЕТЫ ТИПИЧНЫХ «НЕСЧАСТНЫХ»
  3. Статья 630. Типичные условия договора
  4. 5.9. ТИПИЧНЫЙ СЮРПРИЗ
  5. Типичная игра
  6. 2. Типичная игра
  7. 3.10. ТИПИЧНЫЙ ПОТОК ОБРАЗОВ
  8. ПОРТРЕТ ТИПИЧНОГО АГРЕССОРА
  9. ПОРТРЕТ ТИПИЧНОГО АЛКОГОЛИКА
  10. Некоторые типичные сценарии
  11. Некоторые типичные сценарии
  12. Линия времени "во времени"
  13. Типичные ошибки анализа документов в социологическом исследовании
  14. Типичные проблемы самораскрытия. Формирование искаженного образа.