Главная » Java, Структуры данных и алгоритмы » Квадратичная функция времени выполнения алгоритма

0

Решение указанной задачи представлено во фрагменте кода 4.16.

Алгоритм computeSpansl (Р):

Input: массив чисел Л содержащий п элементов.

Output: массив чисел S, содержащий п элементов, причем S[i] является максимальным целым значением к, где к< /+1, а Р [j ] < Р [/ ], при j = / — к + 1,…, /.

for / = 0 to п – 1 do

к <- О

done false repeat

if Р[/ – к] < P[i] then

к <r- к + 1

else

done <r- true until (k > i) or done S[i] <- к return array S

Фрагмент кода 4.16. Алгоритм computeSpansl

Проведем анализ времени выполнения алгоритма computeSpansl.

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

•                                         Алгоритм содержит цикл repeat, вложенный в цикл for. В цикле for используется счетчик /’, и цикл выполняется п раз для / = 0, …, п – 1. Команды цикла for, находящиеся за пределами цикла repeat, выполняются п раз. Таким образом, эти команды плюс увеличение счетчика / и его проверка составляют время выполнения простейших операций О(п).

•                                         При итерации / внешнего цикла for тело внутреннего цикла repeat выполняется максимально / +1 раз. Действительно, в худшем случае элемент S [/] превосходит все предшествующие элементы. Таким образом, проверка условия if (S[/ – k] < S[/]) перед выполнением следующей команды и проверка условия until выполняются / + 1 раз во время итерации / внешнего цикла (/ = 0, …, п – 1). Таким

7 Зак 2456

образом, в худшем случае время выполнения пропорционально 1 +’2 + 3 + … + п. Возвращаясь к утверждению 3.4, можно записать, что время выполнения внутреннего 1дикла составляет 0(п(п + 1)/2), что означает время 0(п2).

Таким образом, время выполнения алгоритма computeSpansl определяется суммой трех составляющих — двух первых элементов вида О(п) и третьего Элемента 0(п2). Таким образом, время выполнения алгоритма computeSpansl есть 0(п2).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии