Содержание
Предисловие |
9 |
||
1. |
Основы анализа алгоритмов |
12 |
|
1.1. |
Что такое анализ? |
14 |
|
|
1.1.1. |
Классы входных данных |
19 |
|
1.1.2. |
Сложность по памяти |
20 |
|
1.1.3. |
Упражнения |
21 |
1.2. |
Что подсчитывать и что учитывать |
22 |
|
|
1.2.1. |
Упражнения |
25 |
1.3. |
Необходимые математические сведения |
26 |
|
|
1.3.1. |
Логарифмы |
26 |
|
1.3.2. |
Бинарные деревья |
27 |
|
1.3.3. |
Вероятности |
28 |
|
1.3.4. |
Упражнения |
31 |
1.4. |
Скорости роста |
32 |
|
|
1.4.1. Классификация скоростей роста |
34 |
|
|
1.4.2. |
Упражнения |
36 |
1.5. |
Алгоритмы вида «разделяй и властвуй» |
37 |
|
|
1.5.1. |
Метод турниров |
41 |
|
1.5.2. |
Нижние границы |
42 |
|
1.5.3. |
Упражнения |
44 |
1.6. |
Рекуррентные соотношения |
45 |
|
|
1.6.1. |
Упражнения |
50 |
1.7. Анализ программ |
51 |
||
2. Алгоритмы поиска и выборки |
53 |
||
2.1. |
Последовательный поиск |
55 |
|
|
2.1.1. |
Анализ наихудшего случая |
56 |
|
2.1.2. |
Анализ среднего случая |
56 |
|
2.1.3. |
Упражнения |
58 |
2.2. Двоичный поиск |
59 |
||
|
2.2.1. |
Анализ наихудшего случая |
61 |
|
2.2.2. |
Анализ среднего случая |
62 |
|
2.2.3. |
Упражнения |
64 |
2.3. |
Выборка |
66 |
|
|
2.3.1. |
Упражнения |
68 |
2.4. Упражнение по программированию |
69 |
||
4 |
Содержание |
|
||
3. |
Алгоритмы сортировки |
70 |
||
|
3.1. Сортировка вставками |
72 |
||
|
|
3.1.1. |
Анализ наихудшего случая |
73 |
|
|
3.1.2. |
Анализ среднего случая |
74 |
|
|
3.1.3. |
Упражнения |
76 |
|
3.2. Пузырьковая сортировка |
77 |
||
|
|
3.2.1. |
Анализ наилучшего случая |
78 |
|
|
3.2.2. |
Анализ наихудшего случая |
78 |
|
|
3.2.3. |
Анализ среднего случая |
79 |
|
|
3.2.4. |
Упражнения |
81 |
|
3.3. |
Сортировка Шелла |
82 |
|
|
|
3.3.1. |
Анализ алгоритма |
84 |
|
|
3.3.2. |
Влияние шага на эффективность |
86 |
|
|
3.3.3. |
Упражнения |
87 |
|
3.4. |
Корневая сортировка |
87 |
|
|
|
3.4.1. |
Анализ |
90 |
|
|
3.4.2. |
Упражнения |
91 |
|
3.5. |
Пирамидальная сортировка |
92 |
|
|
|
3.5.1. |
Анализ наихудшего случая |
95 |
|
|
3.5.2. |
Анализ среднего случая |
97 |
|
|
3.5.3. |
Упражнения |
98 |
|
3.6. |
Сортировка слиянием |
98 |
|
|
|
3.6.1. |
Анализ алгоритма MergeLists |
101 |
|
|
3.6.2. |
Анализ алгоритма MergeSort |
102 |
|
|
3.6.3. |
Упражнения |
104 |
|
3.7. |
Быстрая сортировка |
105 |
|
|
|
3.7.1. |
Анализ наихудшего случая |
107 |
|
|
3.7.2. |
Анализ среднего случая |
108 |
|
|
3.7.3. |
Упражнения |
ПО |
|
3.8. |
Внешняя многофазная сортировка слиянием |
112 |
|
|
|
3.8.1. Число сравнений при построении отрезков |
116 |
|
|
|
3.8.2. Число сравнений при слиянии отрезков |
116 |
|
|
|
3.8.3. |
Число операций чтения блоков |
117 |
|
|
3.8.4. |
Упражнения |
118 |
|
3.9. |
Дополнительные упражнения |
118 |
|
|
3.10. Упражнения по программированию |
120 |
||
4. |
Численные алгоритмы |
123 |
||
|
4.1. |
Вычисление значений многочленов |
125 |
|
|
|
4.1.1. |
Схема Горнера |
126 |
Фреду и Барни
Предисловие
У этой книги две основные задачи -- объяснить, как алгоритмы влияют на эффективность программ, и научить анализировать разнообразные алгоритмы. Глядя на некоторые современные коммерческие программные продукты, понимаешь, что некоторые их создатели не обращают внимания ни на временную эффективность программ, ни на разумное использование памяти. Они полагают, что если программа занимает слишком много места, то пользователь купит дополнительную память, если она слишком долго работает, то он может купить более быстрый компьютер.
Однако скорость компьютеров не может увеличиваться бесконечно. Она ограничена скоростью перемещения электронов по проводам, скоростью распространения света по оптическим кабелям и скоростью коммутации каналов связи компьютеров, участвующих в вычислениях. Другие ограничения связаны не с производительностью компьютеров, а непосредственно со сложностью решаемой задачи. Есть задачи, для решения которых не хватит человеческой жизни, даже если при этом будут использованы самые быстрые из известных алгоритмов. А поскольку среди этих задач есть и важные, необходимы алгоритмы получения приблизительных ответов.
В начале 80-х годов архитектура компьютеров серьезно ограничивала их скорость и объем памяти. Зачастую общий размер программ и данных не превышал 64К. У современных персональных компьютеров эта величина выросла в 1000 раз. Нынешнее программное обеспечение гораздо сложнее, чем в 1980 году, и компьютеры стали заметно
