Главная Промышленная автоматика.

Библиографические примечания

Монография [65] является исчерпывающим обзором по методам сортировки. Метод быстрой сортировки предложен Хоаром (Ноаге) [49], более поздние варианты этой сортировки приведены в [37] и [103]. Пирамидальная сортировка была открыта Видьямсом (Williaffls) [119] и обоснована Фдойдом (Floyd) [34]. Сложность дерева решений для сортировки изучалась в работе [36]. Линейный алгоритм сортировки из раздела 8.7 взят из статьи [13].

Алгоритм Шедда описан в [101], анализ его выполнения приведен в работе [87]. См. также книгу [3], где приведено одно решение упражнения 8.9.



ГЛАВА 9

Методы анализа алгоритмов

Что собой представляет "хороший" алгоритм? Не существует простого ответа на этот вопрос. Многие оценки алгоритмов включают такие субъективные понятия, как простота, понятность или соответствие ожидаемым входным данным. Более объективной (но, возмолшо, не самой валшой) оценкой алгоритма может служить временная эффективность (время выполнение) алгоритма. В разделе 1.5 описывались основные методы определения времени выполнения простых программ. Но в более сложных ситуациях, например при оценке рекурсивных программ, необходимы другие методы. В этой короткой главе рассмотрены некоторые достаточно общие методы решения рекуррентных соотношений, которые возникают при анализе времени выполнения рекурсивных алгоритмов.

9.1. Эффективность алгоритмов

Один из способов определения временной эффективности алгоритма заключается в следующем: на основе данного алгоритма надо написать программу и измерить время ее выполнения на определенном компьютере для выбранного множества входных данных. Хотя такой способ популярен и, безусловно, полезен, он поролсдает определенные проблемы. Определяемое здесь время выполнения зависит не только от используемого алгоритма, но также от архитектуры и набора внутренних инструкций данного компьютера, от качества компилятора, да и от уровня программиста, реализовавшего тестируемый алгоритм. Время выполнения таюке может сушественно зависеть от выбранного множества тестовых входных данных. Эта зависимость становится совершенно очевидной при реализации одного и того же алгоритма с использованием различных компьютеров, различных компиляторов, при привлечении программистов разного уровня и при использовании различных тестовых входных данных. Чтобы повысить объективность оценок алгоритмов, ученые, работающие в области компьютерных наук, приняли асимптотическую временную сложность как основную меру эффективности выполнения алгоритма. Термин эффективность является синонимом этой меры и относится в основном к времени выполнения в самом худшем случае (в отличие от среднего времени выполнения).

Напомним читателю определения 0(f(n)) и П(Дл))данные в главе 1. Говорят, что алгоритм имеет эффективность (т.е. временн(/ю сложность в самом худшем случае) 0(/(л)),или просто /(л), если функция от п, равная максимуму числу шагов, выполняемых алгоритмом, имеет порядок роста 0(/(л)), причем максимум берется по всем входным данным длины п. Молшо сказать по-другому: существует константа с, такая, что для достаточно больших п величина с/(л) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины п.

Существует еще "подтекст" в утверждении, что "эффективность данного алгоритма есть /(л)": время выполнения алгоритма также равно П(/(л)), т.е. /(л) является функцией от га с наименьшей степенью роста, которая ограничивает сверху время выполнения алгоритма в самом худшем случае. Но последнее условие (о наименьшей степени роста) не является частью определения 0(Дл)), часто вообще невозможно сделать никакого заключения о наименьшей степени роста верхней границы.

Наше определение эффективности алгоритма игнорирует константы пропорциональности, которые участвуют в определениях 0(/(л))и Q(f{n)), и для этого есть весомые причины. Во-первых, поскольку большинство алгоритмов записываются на языках программирования высокого уровня, нам приходится описывать их в терми-



нах "шагов", каждый из которых должен выполняться за конечное фиксированное время после трансляции их в машинный язык какого-нибудь компьютера. Однако, как можно точно определить время выполнения какого-либо шага алгоритма, когда оно зависит не только от "природы" самого этого шага, но также от процесса трансляции и машинных инструкций, заложенных в компьютере? Поэтому вместо точной оценки эффективности алгоритма, пригодной только для конкретной машины (и для получения которой надо еше пробраться через запутанные подробности машинных вычислений), используют менее точные (с точностью до константы пропорциональности), но более обшие оценки эффективности в терминах 0(f(n)).

Вторая причина, по которой используются асимптотические оценки и игнорируются константы пропорциональности, заключается в том, что асимптотическая временная сложность алгоритма в большей степени, чем эти константы, определяет граничный размер входных данных, которые можно обрабатывать посредством данного алгоритма. В главе 1 эта ситуация исследована подробно. С другой стороны, читатель должен быть готовым к тому, что при анализе некоторых важных задач (например, сортировки) мы, возможно, будем применять такие утверждения, как "алгоритм А на типовом компьютере выполняется в два раза быстрее, чем алгоритм В".

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

9.2. Анализ рекурсивных программ

в главе 1 мы показали методы анализа времени выполнения программ, не ис-пользуюших рекурсивных вызовов. Анализ рекурсивных программ значительно сложнее и, как правило, требует решения дифференциальных уравнений. Мы будем использовать другие методы, которые похожи на методы решения дифференциальных уравнений, и даже позаимствуем их терминологию.

Сначала рассмотрим пример процедуры сортировки (листинг 9.1). Эта процедура-функция mergesort (сортировка слиянием) в качестве входных данных использует список элементов длиной п и возврашает этот список отсортированным (выходные данные). Эта функция использует также процедуру merge (слияние), у которой входными данными являются два отсортированных списка Ly и Ьг- Процедура merge(Li,L2) просматривает эти списки поэлементно, начиная с наибольших элементов. На каждом шаге наибольший элемент из двух сравниваемых (наибольшие элементы из списков Li и Lj) удаляется из своего списка и помешается в выходные данные. В результате получается один отсортированный список, содержаший все элементы из списков Ly и Ьг. Детали выполнения процедуры merge сейчас для нас не имеют значения, сортировка слиянием подробно рассмотрена в главе 11. Сейчас для нас важно только то, что процедура merge на списках длиной п/2 выполняется за время порядка 0(п).

Листинг 9.1. Рекурсивная процедура сортировки слиянием

fimction mergesort ( L: list; n: integer ) : list { L - список типа list длиной п.

Предполагается, что л является степенью числа 2 }

il, 12: list begin

if л = 1 then





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 [84] 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.005