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

0

Существует более эффективный способ вычисления интервалов. Можно отметить, что интервал j/ на определенный день / легко вычисляется, если известен ближайший к дню / день, курс акций в который был больше, чем в этот день (см. рис. 4.12). Если для дня / существует такой предшествующий день, обозначим его h(i), в противном случае пусть h{i) = -1. Интервал для дня / равен 57 – / – h(i).

В другом алгоритме, приведенном во фрагменте кода 4.17, в качестве вспомогательной структуры данных используется стек, в котором хранятся значения дней /, й(/), h(h(ij) и т.д. Переходя от дня / — 1 к дню /, повторно извлекаем из стека дни, курс акций в которые меньше или равен ри

Пример выполнения алгоритма computeSpans2 представлен на рис. 4.13.

Алгоритм; computeSpans2(/3):

Input; массив чисел Р, содержащий п элементов, и пустой стек D.

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

for / = 0 to п – 1 do done <- faJse

while not (P.isEmpty() or done ) dq if P[i] > P[D.top()] then

D.popO else

done <- true if D.isEmpty() then h -1 else

h <- D.top() S[i] <r- i – h D.push (/)

return

Фрагмент кода 4.17. Алгоритм computeSpans2

Л/с. 4.72. Ежедневный курс акций; стрелки указывают ближайший день с более высоким курсом акций

Предположим, что при реализации стека D каждый метод АТД выполняется за время 0(1). На основании этого проведем анализ времени выполнения алгоритма computeSpans2.

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

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

•          Рассмотрим выполнение внутреннего цикла while при итерации / внешнего цикла for. Команда done true выполняется максимум один раз, так как она приводит к выходу из цикла. Пусть — число раз выполнения команды D.рор(). Каждое условие (not (Z).isEmpty() or done)) и (P[i] > P[D.top()]) проверяется максимально 1 раз.

Таким образом, общее время выполнения операций в цикле while будет:

/toe. 4.7J. Пример выполнения алгоритма computeSpans2. Содержимое стека после завершения каждой итерации цикла for наглядно представлено с помощью выделенных точечным штрихом столбцов, обозначающих дни в стеке А и стрелок. Столбцы, обозначенные удлиненным штрихом, показывают дни, которые еще не обработаны алгоритмом. Закрашенные столбцы обозначают дни, удаленные из стека D пр# текущей итерации

Другими словами, общее время выполнения операций цикла while составляет О(п). Таким образом, время выполнения алгоритма computeSpans2 определяется суммой трех компонентов, каждый из которых равен 0(п), и общее время выполнения алгоритма computeSpans2 есть О(п).

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

По теме:

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