Глава 2

Основы анализа алгоритмов

Основной задачей анализа алгоритмов является выявление закономерности мас- штабирования требований к ресурсам (затраты времени и памяти) с возрастанием размера входных данных.

В начале этой главы речь пойдет о том, как эта концепция применяется в конкретных ситуациях, так как конкретизация помогает понять суть понятия вычислительной разрешимости. После этого будет разработан математи- ческий механизм, необходимый для описания закономерностей скорости роста различных функций с увеличением размера входных данных; он помогает точно определить, что же понимается под выражением «одна функция растет быстрее другой».

Затем мы разработаем граничные оценки времени выполнения некоторых базо- вых алгоритмов, начиная с реализации алгоритма Гейла-Шепли из главы 1. Далее в обзор будут включены оценки времени выполнения и некоторые специфические характеристики алгоритмов, обеспечивающие это время выполнения. В некоторых случаях достижение хорошего времени выполнения зависит от использования бо- лее сложных структур данных, и в конце главы будет рассмотрен очень полезный пример такой структуры данных: приоритетные очереди и их реализация на базе кучи (heap).

2.1.

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

Еще по теме Глава 2:

  1. Глава 8. Глава государства в зарубежных странах
  2. Глава рода
  3. Глава рода
  4. Глава 1
  5. Глава 2
  6. Глава 3
  7. Глава 4
  8. Глава 5
  9. Глава 6
  10. ГЛАВА 1.
  11. ГЛАВА 2.
  12. ГЛАВА 3.
  13. ГЛАВА 5.
  14. ГЛАВА 6.
  15. ГЛАВА 7.