Оценка сложности алгоритма до порядка является верхней границей сложнос-
ти алгоритмов. Если программа имеет больший порядок сложности, это не означа-
ет, что алгоритм будет действительно выполняться так долго. При задании правиль-
ных данных выполнение многих алгоритмов занимает гораздо меньше времени, чем
можно предположить на основании порядка их сложности. Например, следующий
код иллюстрирует простой алгоритм, который определяет расположение элемента
в списке.
function Locateltem(target : Integer) : Integer;
var
i : Integer;
begin
for i := 1 to N do
if (Value(i]=target) then
, .
begin
Result := i;
break;
end;
end;
Если искомый элемент находится в конце списка, то программе придется ис-
следовать все N элементов списка, чтобы обнаружить нужный. Это займет ty ша-
гов, и сложность алгоритма будет равна O(N). В данном, так называемом наихуд-
шем случае (worst case) время работы алгоритма будет максимальным.
С другой стороны, если искомый число расположено в самом начале списка,
алгоритм завершит работу почти сразу же. Он выполнит несколько шагов, прежде
чем найдет искомый номер и остановится. Это наилучший случай (best case) со
сложностью порядка О(1). Строго говоря, подобный случай не очень интересен,
поскольку он вряд ли произойдет в реальной жизни. Интерес представляет сред-
ний или ожидаемый вариант (expected case) поведения алгоритма.
Если номера элементов в списке изначально беспорядочно смешаны, то иско-
мый элемент может оказаться в любом месте списка. В среднем потребуется ис-
следовать N/2 элементов для того, чтобы найти требуемый. Значит, сложность это-
го алгоритма в усредненном случае будет порядка O(N/2), или O(N), если убрать
постоянный множитель.
Для некоторых алгоритмов наихудший случай сильно отличается от ожидаемо-
го случая. Например, алгоритм быстрой сортировки, описанный в главе 9, имеет
наихудший случай поведения О(№), а ожидаемое поведение равно O(N * log(N)),
что гораздо быстрее. Алгоритмы, подобные алгоритму быстрой сортировки, иногда
делают очень длинными, чтобы исключить возникновение наихудшего случая по-
ведения.
Читать дальше >>