Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 1.1. Поиск максимального элемента в массиве 
int max = a[0]; 
// 
повторяется 1 раз 
int i_max = 0; 
// 
повторяется 1 раз 
for(int i = 1; i < N; i++) 
// 
повторяется N раз 
if (a[i] > max) // 
повторяется N - 1 раз 
{ 
max = a[i];
// 
повторяется m раз 
i_max = i;
// 
повторяется m раз 
} 
Число повторений двух последних действий m зависит от значений 
элементов массива. Очевидно, что 0 ≤ m < N. Суммируя число повторений 
каждого действия алгоритма и обозначая среднее время выполнения одного 
действия t, получим следующее значение времени работы алгоритма: 
( )
(
)
(
)
2
1
2
2
2
1 .
T N
t Nt
N
t
mt
N
m
t
= +
+
−
+
=
+
−
(1.1) 
При анализе алгоритмов оценку их эффективности делают, исходя из 
предположения о наихудшем с точки зрения времени выполнения сочетании 
6 / 23

---

7 
значений исходных данных. Обоснованность такого подхода очевидна: худ-
шего результата алгоритм никогда не покажет, но может показать гораздо 
лучший.
Для рассмотренного алгоритма наихудшим является случай, когда мас-
сив упорядочен по возрастанию и, соответственно, m = N – 1. Тогда T(N) = 
= (4 N – 3) t, т. е. время работы алгоритма является линейной функцией от 
размерности задачи.
Временная эффективность алгоритмов может выражаться полиномами 
второй и более высоких степеней от размерности задачи. Во всех случаях 
такой полиномиальной зависимости переход к пределу больших n заключа-
ется в отбрасывании всех членов полинома, кроме старшего. В результате мы 
приходим к понятию скорости роста (rate of growth) для алгоритма, т. е. за-
кону изменения времени выполнения алгоритма от размерности задачи. Для 
обозначения скорости роста алгоритмов используется так называемая 
O-нотация, которая определяется следующим образом [27, 40].