Глава 2
Основной задачей анализа алгоритмов является выявление закономерности мас- штабирования требований к ресурсам (затраты времени и памяти) с возрастанием размера входных данных.
В начале этой главы речь пойдет о том, как эта концепция применяется в конкретных ситуациях, так как конкретизация помогает понять суть понятия вычислительной разрешимости. После этого будет разработан математи- ческий механизм, необходимый для описания закономерностей скорости роста различных функций с увеличением размера входных данных; он помогает точно определить, что же понимается под выражением «одна функция растет быстрее другой».Затем мы разработаем граничные оценки времени выполнения некоторых базо- вых алгоритмов, начиная с реализации алгоритма Гейла-Шепли из главы 1. Далее в обзор будут включены оценки времени выполнения и некоторые специфические характеристики алгоритмов, обеспечивающие это время выполнения. В некоторых случаях достижение хорошего времени выполнения зависит от использования бо- лее сложных структур данных, и в конце главы будет рассмотрен очень полезный пример такой структуры данных: приоритетные очереди и их реализация на базе кучи (heap).
2.1.
Еще по теме Глава 2:
- Глава 8. Глава государства в зарубежных странах
- Глава рода
- Глава рода
- Глава 1
- Глава 2
- Глава 3
- Глава 4
- Глава 5
- Глава 6
- ГЛАВА 1.
- ГЛАВА 2.
- ГЛАВА 3.
- ГЛАВА 5.
- ГЛАВА 6.
- ГЛАВА 7.