Подразделы

Другие разделы

Дата и время

16/03/2025 03:11:13

Авторизация

Основы анализа алгоритмов

Эффективность алгоритмов Оценка размера входных данных Единицы измерения времени выполнения алгоритма Порядок роста Эффективность алгоритма в разных случаях

Эффективность алгоритма в разных случаях

Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но также и от особенностей конкретных входных данных. В качестве примера рассмотрим задачу последовательного поиска. Она решается с помощью довольно простого алгоритма, который выполняет поиск заданного элемента (ключа поиска $K$ ) в списке, состоящем из $n$ элементов, путем последовательного сравнения ключа $K$ с каждым из элементов списка. Работа алгоритма завершается, либо когда заданный ключ найден, либо когда весь список исчерпан.

Алгоритм SequentialSearch ( $A, K$ )
// Входные данные: массив чисел $A$ [0.. $n-1$ ] и ключ поиска $K$
// Выходные данные: возвращается индекс первого элемента
// массива $A$ , который равен $K$ , либо $-1$
$i larr 0$
while $i < n$ and $A_i != K$ do
$quad i larr i + 1$
if $i < n$
$quad$ return $i$
else
$quad$ return $-1$

Совершенно очевидно, что время работы этого алгоритма может отличаться в очень широких пределах для одного и того же списка размера $n$ . В наихудшем случае, т.е. когда в списке нет искомого элемента либо когда искомый элемент расположен в списке последним, в алгоритме будет выполнено наибольшее количество операций сравнения ключа со всеми $n$ элементами списка: $C_{"worst"} (n) = n$ .

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

Способ определения эффективности алгоритма для наихудшего случая в принципе несложен: нужно проанализировать алгоритм и выяснить, для каких из возможных комбинаций входных данных размером $n$ значение числа основных операций алгоритма $C(n)$ будет максимальным, а затем вычислить значение $C_{"worst"} (n)$ для наихудшего случая.

Анализ эффективности алгоритма для наихудшего случая позволяет получить очень важную информацию о быстродействии алгоритма в целом, так как для любых исходных данных размером $n$ время выполнения алгоритма не будет превышать максимально возможного значения $C_{"worst"} (n)$ получаемого для наихудшей совокупности входных данных.

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

Например, для алгоритма последовательного поиска наилучшим случаем входных данных будет такой список размером $n$ , первый элемент которого равен ключу поиска $K$ . Поэтому для него $C_{"best"} (n) = 1$ .

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

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

Например, для алгоритма сортировки методом вставок наилучший случай входных данных соответствует заранее отсортированному массиву. Причем она лишь ненамного ухудшается в случае, если входной массив почти отсортирован. Следовательно, такой алгоритм очень хорошо подойдет для случаев, когда приходится иметь дело с почти отсортированными массивами.

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

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

Для этого нужно сделать ряд предположений о типовой совокупности входных данных размером $n$ .

Вернемся к алгоритму поиска методом последовательного перебора. Сделаем два предположения:

вероятность успешного поиска равна $p$ , где $0 <= р <= 1$ ;
вероятность первого совпадения ключа с $i$ -м элементом списка одинакова для любого $i$ .

Исходя из этих предположений, можно вычислить среднее количество операций сравнения с ключом $C_{"avg"} (n)$ .

Если совпадение с ключом найдено, вероятность того, что это произошло именно на $i$ -м элементе списка, равна $p//n$ для любого $i$ . При этом количество операций сравнения равно $i$ . Если совпадение с ключом не найдено, количество операций сравнения равно $n$ , а вероятность этого события равна $(1 — p)$ . Поэтому
$C_{"avg"} (n)=[1*p/n+2*p/n+...n*p/n]+n*(1-p)=$
$=p/n*[1+2+...+n]+n*(1-p)=$ $=p/n*(n*(n-1))/2+n*(1-p)=p/2+n-(p*n)/2$

Например, если $p = 1$ (т.е. элемент, равный ключу, точно есть в списке), среднее количество операций сравнения будет равно $(n + 1)//2$ , т.е. в среднем в алгоритме проверяется половина элементов списка. Если $p = 0$ (т.е. искомого элемента в списке нет), среднее количество операций сравнения будет равно $n$ , поскольку при этом в алгоритме проверяются все $n$ элементов списка.

Определение эффективности алгоритма для среднего случая более трудная задача, чем для наихудшего и наилучшего случаев. При использовании прямого метода для решения этой задачи, необходимо разбить всю совокупность экземпляров входных данных размером $n$ на несколько групп так, чтобы для каждой группы число основных операций, выполняемых алгоритмом, было одинаково. Затем нужно найти или придумать функцию распределения вероятностей для входных данных и с ее помощью вычислить ожидаемое значение количества основных операций алгоритма. Технически реализовать этот план не составит большого труда, хотя проверить вероятностные предпосылки, лежащие в его основе, обычно очень тяжело.

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

Из приведенного анализа понятно, что эффективность алгоритма для среднего случая нельзя получить, усреднив его эффективности для наихудшего и наилучшего случаев.

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

Задания для практики

В ящике хранится 22 перчатки: 5 пар красных, 4 пары желтых и 2 пары зеленых. Предположим, что вы выбираете их в темноте наугад и можете проверить, что именно вы выбрали, только после того, как выбор сделан. Чему равно минимальное количество перчаток, которые надо взять из ящика, чтобы получить как минимум одну пару перчаток одинакового цвета? Дайте ответ на этот вопрос для наилучшего и наихудшего случая.
Предположим, у вас есть 5 разных пар носков, и вы обнаружили, что два носка потеряны. Естественно, вы заинтересованы в том, чтобы в результате осталось наибольшее количество полных пар, поскольку носить разные носки вы не будете. Поэтому в лучшем случае у вас останется 4 полных пары, а в худшем — только 3. Предположим, вы имеете равные шансы потерять любой из 10 носков. Определите вероятности наилучшего и наихудшего случаев, а также количество пар носков, которые остаются у вас в среднем случае.