Подразделы

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

Дата и время

09/04/2025 22:40:59

Авторизация

Зарегистрироваться
Восстановить пароль

Анализ алгоритмов

Анализ нерекурсивного алгоритма Анализ рекурсивного алгоритма Эмпирический анализ

Анализ нерекурсивного алгоритма

Пример анализа нерекурсивного алгоритма

Алгоритм MaxElement( $A$ )
// Входные данные: массив чисел $A[0...n-1]$
// Выходные данные: возвращается значение наибольшего
// элемента массива $А$
$m larr A[0]$
for $i in [1...n-1]$ do
$quad$ if $A[i] >m$
$quad quad m larr A[i]$
return $m$

Очевидно, что в этом алгоритме размер входных данных нужно оценивать по количеству элементов в массиве, т.е. числом $n$ . Операции, выполняемые чаще всего, находятся во внутреннем цикле for алгоритма.

Таких операций две: сравнение ( $A[i] > mx$ ) и присваивание ( $mx larr A[i]$ ). Поскольку сравнение выполняется на каждом шаге цикла, а присваивание – нет, логично считать, что основной операцией алгоритма является операция сравнения.

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

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

$C(n)=sum_{i=1}^{n-1} 1 = n-1 in Theta(n)$

Общий план анализа эффективности нерекурсивных алгоритмов

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

Алгоритм UniqueElements( $A$ )
// Входные данные: массив вещественных чисел $А[0...n-1]$
// Выходные данные: возвращается значение "true", если все
// элементы массива А различны, и "false" в противном случае
for $i in [0...n-2]$ do
$quad$ for $j in [i + 1...n-1]$ do
$quad quad$ if $A[i]=A[j]$
$quad quad quad$ return false
return true

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

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

Наихудший случай входных данных может возникнуть при обработке массивов двух типов: а) в которых нет одинаковых элементов; б) в которых два одинаковых элемента находятся рядом и расположены в самом конце массива.

В цикле выполняется одна операция сравнения. При этом переменная цикла $j$ последовательно принимает значения от $i + 1$ до $n-1$ . Внутренний цикл каждый раз повторяется при каждом выполнении внешнего цикла. При этом переменная внешнего цикла $i$ последовательно принимает значения от 0 до $п - 2$ . Таким образом, получаем:

$C_{"worst"}(n)=sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} 1 = sum_{i=0}^{n-2} (n-1 +i) =$
$=sum_{i=0}^{n-2} (n-1) +sum_{i=0}^{n-2} i= (n-1)^2+((n-1)*(n-2))//2=$
$=((n-1)*n)/2=1/2 n^2-1/2 n in Theta(n^2)$

Алгоритм SumDigits( $n$ )
// Входные данные: целое положительное число $n$
// Выходные данные: сумма цифр числа
$s larr 0$
while $n>0$ do
$quad s larr s+ n mod 10$
$quad n larr |__ n//10 __|$
return $s$

В качестве основных операций можно рассматривать сравнение с 0, деление, сложение, остаток от деления, 2 присваивания. Количество операций $C(n)$ зависит от $n$ и равно $|__ log_{10} n __| + 1$ . $C(n) in Theta(log_2 n)$

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

Рассмотрим следующий алгоритм.

Алгоритм Secret( $A$ )
// Входные данные: массив вещественных чисел $А[0...n-1]$
$M larr A[0]$
for $i in [0...n-1]$ do
$quad$ for $j in [i...n-1]$ do
$quad quad$ $S larr 0$
$quad quad$ for $k in [i...j]$ do
$quad quad quad quad S larr S+A[k]$
$quad quad$ if $S>M$
$quad quad quad quad M larr S$
return $M$

а) Что вычисляется с помощью этого алгоритма?
б) Назовите основную операцию алгоритма.
в) Сколько раз выполняется основная операция?
г) К какому классу эффективности относится этот алгоритм?
д) Усовершенствуйте этот алгоритм или предложите другой алгоритм и оцените его класс эффективности. Если вам не удастся этого сделать, попытайтесь доказать, что это невозможно

Назад