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

0

В заключение главы приведем анализ двух алгоритмов, которые разрешают одну и ту же задачу, однако время выполнения которых существенно различается. Задача состоит в вычислении так называемых префиксных средних значений последовательности чисел. В частности, пусть X— массив из п чисел, необходимо создать массив А, в котором A[i] является средним значением элементов А[0], Х[1],…, Х[\], где / = 0,…, п – 1, то есть

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

Квадратичная функция времени выполнения алгоритма

В первом примере решения задачи вычисления префиксных средних значений рассмотрим алгоритм prefixAveragesl, представленный во фрагменте кода 3.4. Согласно определению, он вычисляет каждый элемент А по отдельности.

Алгоритм prefixAveragesl^):

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

Output: массив чисел А, содержащий п элементов, причем A[i ] является средним значением элементов ^[0], …, Х\7].

Пусть А есть массив из п элементов.

for / <- 0 to п- 1 do

а <-0

for y<-0to / do

a<-a + X[J]

A [/] <— я / (/ + 1)

Фрагмент кода 3.4. Алгоритм prefixAveragesl

Проведем анализ алгоритма prefixAveragesl.

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

•                   Алгоритм содержит два вложенных for-цикла, в которых используются счетчики / и j соответственно. Тело внешнего цикла, со счетчиком /, выполняется п раз для / = 0, …, п – 1. Таким образом, операции а — 0 и A[i ] = а /(/ + 1) выполняются п раз каждая. Таким образом, эти две операции плюс увеличение счетчика и его проверка составляют число простейших операций, пропорциональное п, то есть время 0{п).

•                   Тело внутреннего цикла со счетчиком j выполняется / + 1 раз в зависимости от текущего значения счетчика внешнего цикла /. Таким образом, операция а = а + X[j] внутреннего циющ выполняется 1+2 + 3 + … + п раз. Согласно утверждению 3.4, можно записать 1 + 2 + 3 + … + « = п{п + 1)/2, что означает время выполнения внутреннего цикла есть 0(п2). Для определения времени простейших операций, выполняемых при увеличении и проверке счетчика у, используется та же схема доказательства — оно также составляет 0(п2).

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

Линейная функция времени выполнения алгоритма

Для более эффективного вычисления префиксных средних значений \южно предположить, что последовательные средние значения A[i~ 1] и A[i ] равны:

A[i -1]                           + +…+ X[i -1]) / /

A[i] =(*[0] + X[l] +…+ X[i -1] + X[i] / (/ + 1)).

Допустим, есть префиксная сумма .Y[0] + Х[\] + … + Х{\], тогда префиксные средние значения можно вычислить по формуле A[i] = Sj/(i + 1). Текущее значение префиксной суммы легко определить с помощью цикла, просматривающего массив X. Рассмотрим алгоритм prefixAverages2, представленный во фрагменте кода 3.5.

Алгоритм prefixAverages2:

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

Output: массив чисел А, содержащий п элементов, причем A[i ] является средним значением элементов Х[0], …, X[i], Пусть А — массив из п элементов.

s <— О

for /<- 0 to л – 1 do

s <— s + X [/] А [/] <- s/(i + 1) return array А

Фрагмент кода 3.5. Алгоритм prefixAverages2

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

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

•                   Для инициализации переменной s в начале алгоритма требуется 0(1) времени.

• Алгоритм содержит один цикл for, в котором используется счетчик /. Тело цикла выполняется п раз для / = 0, …, п – 1. Таким образом, операции s = s + Х[‘\] и А[i] = s/(i + 1) выполняются п раз каждая. Полученные результаты означают, что данные операции плюс увеличение счетчика / и его проверка составляют число простейших операций, пропорциональное п, то есть время О(п).

Таким образом, время выполнения алгоритма prefixAverages2 определяется суммой трех составляющих. Первый и третий элемент вида О(п) и второй элемент 0(1). Используя утверждение 3.6, получаем, что время выполнения алгоритма prefixAverages2 равно 0(п), что является более приемлемым по сравнению с алгоритмом prefixAveragesl, время выполнения которого определяется квадратичной функцией.

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

По теме:

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