Начало
Учебные материалы
Анализ алгоритмов
Анализ нерекурсивного алгоритма
Алгоритм 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)`
--
##### Общий план анализа эффективности нерекурсивных алгоритмов
1. Выберите параметр (или параметры), по которому будет оцениваться
размер входных данных алгоритма.
2. Определите основную операцию алгоритма. Как правило, она
находится в наиболее глубоко вложенном внутреннем цикле алгоритма.
3. Проверьте, зависит ли число выполняемых основных операций только
от размера входных данных. Если оно зависит и от других факторов,
рассмотрите при необходимости, как меняется эффективность
алгоритма для наихудшего, среднего и наилучшего случаев.
4. Запишите сумму, выражающую количество выполняемых основных
операций алгоритма.
5. Используя стандартные формулы и правила суммирования, упростите
полученную формулу для количества основных операций алгоритма.
Если это невозможно, определите хотя бы их порядок роста.
--
Алгоритм 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)`
---
##### Задания для практики
1. Рассмотрим следующий алгоритм.
Алгоритм 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`
а) Что вычисляется с помощью этого алгоритма?\
б) Назовите основную операцию алгоритма.\
в) Сколько раз выполняется основная операция?\
г) К какому классу эффективности относится этот алгоритм?\
д) Усовершенствуйте этот алгоритм или предложите другой алгоритм и оцените его класс
эффективности. Если вам не удастся этого сделать, попытайтесь доказать, что это
невозможно
