САОД Методы анализа, страница 6

а) в которых нет одинаковых элементов;

б) в которых два одинаковых элемента находятся рядом и расположены в самом конце массива.

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

Обратите внимание, что этот результат можно было легко предсказать: в рас­сматриваемом алгоритме в самом худшем случае для массива, состоящего из n элементов, нужно сравнить между собой все (n–1)n /2 различных пар элементов.

Пример 3. Для двух заданных матриц А и В размером n х n определите временную эффективность алгоритма их умножения С = АВ, основанного на опре­делении этой операции. По определению С – это матрица размером n х n, эле­менты которой являются скалярными произведениями соответствующих строки матрицы А ни столбца матрицы В, как показано ниже.

АЛГОРИТМ MatrixMultiplication (A [0..n – 1, 0.. n – 1],

В [0.. n – 1, 0.. n – 1])

// Выполняется умножение двух квадратных матриц

// размером n х n. Используется алгоритм,

// основанный на определении этой операции

// Входные данные: две квадратные n х n матрицы А к В

// Выходные данные: матрица С = АВ

BEGIN

FOR i 0 TO n-1 DO

FOR j 0 TO n-1 DO

C[i,j] 0.0

FOR k 0 TO n-1 DO

C[i,j] C[i,j]+A[i, k]*B[k,j]

RETURN C

END

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

Вполне очевидно, что на каждом шаге внутреннего цикла алгоритма выпол­няется только одна операция умножения. При этом значение переменной цикла k последовательно изменяется от нижней границы 0 до верхней границы n – 1. Поэтому количество операций умножения, выполняемых для каждой пары значений переменных i и j, можно записать следующей тройной суммой:

Для вычисления значения этой суммы воспользуемся формулами из следующего раздела:

.

Рассматриваемый алгоритм достаточно прост.

Время выполнения алгоритма на конкретном компьютере можно оценить с помощью следующего произведения:

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

где с_а ~ время выполнения одной команды сложения. Обратите внимание, что полученная оценка отличается от прежней только постоянным множителем, а не порядком роста.

1.3.10Формулы, использующиеся при анализе алгоритмов

Свойства логарифмов

В приведенных ниже формулах основание алгоритмов считается большей 1; его конкретная величина значения не имеет. Запись

lg a означает логарифм по основанию 10;

— логарифм по основанию ;

х и у — произвольные положительные числа.

Комбинаторика

1. Количество перестановок n-элементного множества:

2. Количество k-комбинаций n-элементного множества (сочетаний элементов из n):

3. Количество подмножеств n-элементного множества:

Значение суммы некоторого ряда

1.

2.

3.

4.

5.

6.

7.

8.

(эта сумма называется n-ым гармоническим числом и обозначается ; константа называется константой Эйлера)

9.

Правила работы с суммами

1.

2.

3.

4.

5.

Литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: "Вильямс", 2001. – 384 с.

3. Бентли Д. Жемчужины творчества программистов. – М.: Радио и связь, 1990.

4. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

5. Вирт Н. Алгоритмы и структуры данных. – М: Мир, 1989. – 360 с.

6. Грин Д., Кнут Д. Математические методы анализа алгоритмов. – М: Мир, 1987.

7. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.

8. Дейкстра Э. Дисциплина программирования. – М: Мир, 1978.

9. Кнут Д.Е. Искусство программирования для ЭВМ. В 3-х томах. – М.: Мир, 1976.

10. Кнут Д.Е. Искусство программирования. В 3-х томах. – М.: "Вильямс", 2000.

11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 2005.

12. Лэгсам Й., Огенстайн М. Структуры данных для персональных ЭВМ. – М.: Мир, 1989. – 586с.

13. Оре О. Графы и их применение. – М.: Мир, 1965.

14. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.

15. Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М: Мир, 1986. – 218 с.

16. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.

17.  Харари Ф. Теория графов. – М: Мир, 1973.

18. Левитин А.В. Алгоритмы: введение в разработку и анализ.: Пер. с англ.– М.:Издательский дом «Вильямс», 2006. – 576.

Русскоязычные ресурсы InterNet

1. http://algo.4u.ru/

2. http://algolist.manual.ru/

3. http://alglib.chat.ru/

4. http://algo.do.ru/

5. http://hcinsu.chat.ru/

6. http://algolist.da.ru/

7. http://progstone.narod.ru/links/wantalgo.html

8. http://www.sevmashvtuz.edu/links/algorithms.html

© МГУПИ, 2009

_______________________________________________________________

Лицензия ЛР №_______ от _______ г.

Подписано к печати Формат 60х84 1/16 Бумага тип №3

Печать офсетная Усл. печ. л Тираж ___ экз.

_______________________________________________________________

Редакционно-издательский отдел

Отдел оперативной полиграфии МГУПИ

107996, Москва, ул. Стромынка, 20