Анализ алгоритмов. Модель вычислений
Анализ алгоритмов означает измерение и описание их характеристик. При этом обычно наибольшее внимание уделяется необходимому объему памяти и затратам времени на выполнение алгоритма. Память и время как правило являются независимыми ресурсами, но часто оказывается возможным ограничить затраты одного из видов ресурсов за счет другого, что иногда оценивается в виде отношения память / время.
Для анализа алгоритма сначала нужно идентифицировать операции, которые в нем используются, и стоимость каждой из них. Это определяется моделью вычислений.
Модель вычислений определяет набор допустимых элементарных операций и стоимости этих операций.
Элементарные операции – это такие операции, для каждой из которых назначена фиксированная стоимость, хотя эта стоимость неодинакова для разных элементарных операций.
Числовые алгоритмы обычно анализируются путем подсчета арифметических операций. Алгоритмы сортировки и поиска анализируются путем подсчета количества сравнений пар элементов. Стоимость каждой операции устанавливается в абстрактных единицах времени, называемых шагами. Время работы алгоритма для указанных входных данных равно общему числу выполняемых шагов.
Рассмотрим в качестве примера задачу поиска заданного числа х в отсортированном массиве целых чисел. Назовем эту задачу ПОИСК: Для заданного целого числа х и отсортированного массива а различных целых чисел сообщить индекс числа х внутри массива а, если такого числа в массиве а нет, то возвращаемое значение должно быть равно -1.
Модель вычислений, которую можно принять для задачи ПОИСК, содержит операцию типа ПРОБА: сравнение числа х с некоторым целым числом в массиве. В предположении, что целые числа ограничены по величине, одиночная проба может быть выполнена за постоянное время. Так, что можно считать, что стоимость пробы составляет один шаг.
Простейшее решение ПОИСКА может быть реализовано путем последовательного поиска: пошаговый просмотр массива а с пробой каждого целого числа.
F:=false;
For i:=1 to N do
if (a[i]=x) then begin write(i); f:=true; end;
if not(f) then write(‘-1’);
Если время этой программы обозначить функцией от введенных данных через F(x,a,N), то имеем:
в противном случае (поиск неудачен)
При оценке алгоритма можно использовать меру сложности для наихудшего случая, в среднем или при средневзвешенном анализе.
Время работы в наихудшем случае определяется для самого длительного выполнения алгоритма для любых входных данных при каждом размере ввода (при любом количестве данных). В примере в наихудшем случае выполняется n проб и время работы алгоритма T(n)=n. Время в наихудшем случае обычно вычислить достаточно просто и такая характеристика часто определяется видом входных данных.
Время работы в среднем определяет усредненное значение времени работы для всех видов входных данных для каждого размера. В примере оно равно (n+1)/2 в предположении, что каждый из n элементов может быть выбран с равной вероятностью и что поиск завершается успешно. Если второе предположение не удовлетворяется, то время работы в среднем лежит в диапазоне [(n+1)/2, n] в зависимости от причины. Анализ ситуации в среднем обычно более трудный по сравнению с анализом наихудшего случая, поскольку он существенно зависит от определения, что считать типичным вводом.
Операции, выполняемые алгоритмом, обычно взаимозависимы. Параметры каждой операции, например, их стоимость зависят от того, что происходило перед этим. В некоторых алгоритмах невозможно обеспечить наихудшие условия для всех операций одновременно. В более общем случае, стоимость сравнительно дорогих операций может быть перекрыта большим числом недорогих операций. При средневзвешенном анализе делается попытка учесть такую ситуацию: учитывается средняя стоимость каждой операции в худшем случае.
Рассмотрим алгоритм, в котором выполняются n операций с многодоступным стеком S. В этой структуре данных выполняются операции:
s.push(x) – занесение элемента x на верх стека S.
s.pop(i) – выборка i самых верхних элементов из стека S. Операция не определена, если стек S содержит менее i элементов.
Предположим, что операция s.push(x) выполняется за постоянное время (за 1 шаг), а операция s.pop(i) – за время, пропорциональное i, т.е. за i шагов.
Средневзвешенный анализ будем проводить используя веса. При взвешенной стоимости операции вес может быть больше или меньше фактической стоимости операции. Недорогим операциям обычно приписывается взвешенная стоимость, которая превышает их действительную стоимость, а наиболее дорогим – меньше. Это обусловлено желанием уравновесить операции, за счет недорогих операций перекрыть стоимость дорогих.
Операция |
Фактическая стоимость |
Взвешенная стоимость |
s.push(x) |
1 |
2 |
s.pop(i) |
i |
0 |
При каждой записи элемента в стек на счет оплаты операции относится один шаг, а второй шаг хранится в резерве. Тогда при выборке из стека i элементов стоимость операции будет оплачена i шагами, которые были накоплены в резерве – по одному шагу за каждый вызванный элемент.
Общая взвешенная стоимость достигается максимума при непрерывности последовательности n операций записи в стек и составляет 2n шагов. Следовательно, в среднем в наихудшем случае каждая операция выполняется за два шага.
Взвешенный анализ часто применяется для поиска верхней границы времени работы алгоритма в наихудшем случае: устанавливается зависимость количества операций, выполняемых алгоритмом, от размера ввода и затем вычисляется взвешенная стоимость каждой операции.