Время работы алгоритма

Question

Извините, это вопрос из трех частей.Я продолжаю пытаться получить первую часть, и я думаю, что если я получу это, все остальное встанет на свои места, но мое время работы не совсем правильное.Я понимаю, что существует n итераций, но не то, как рассчитать количество итераций внутреннего цикла без использования значения j

. Рассмотрим следующую основную проблему.Вам дан массив A, состоящий из n целых чисел A [1], A [2], ... A [n].Вы хотите вывести двумерный массив B размером n на n, в котором B [i, j] (для i = j, поэтому не имеет значения, что выводится для этих значений.) Вот простой алгоритмрешить эту проблему.

For i=1, 2,...,n
    For j=i+1, i+2, ... n
        Add up array entries A[i] through A[j]
        Store the result in B[i,]]
    Endfor
 Endfor

(a) Для некоторой функции f, которую вы должны выбрать, задайте границу формы O (f (n)) для времени выполнения этого алгоритма на входе размераn (т. е. ограничение числа операций, выполняемых алгоритмом).

(b) Для этой же функции f покажите, что время выполнения алгоритма на входе размера n также составляет ~ 2(е (п)).(Это показывает асимптотически жесткую границу ® (f (n)) во время выполнения.)

(c) Хотя алгоритм, который вы проанализировали в частях (a) и (b), является наиболее естественным способомрешить проблему - в конце концов, он просто перебирает соответствующие записи массива B, заполняя значения для каждого - он содержит некоторые крайне ненужные источники неэффективности.Дайте другой алгоритм для решения этой проблемы с асимптотически лучшим временем выполнения.Другими словами, вы должны разработать алгоритм со временем выполнения O (g (n)), где limn -> бесконечность g (n) / f (n) = O.

Answer 1

Суммирование от A[i] до A[j] равно j - i + 1, f(n) = \sum_{i=1}^n\sum_j={i+1}^n (j-i+1) + 1, которое 1 предназначено для добавления значения к B[i,j].Следовательно, изменением переменной из k = j - i + 1, f(n) = \sum_{i=1}^n \sum_{k=0}^{n-i+1}k = \sum_{i=1}^n (n-i +1)(n - i + 2)/2.Путем изменения переменной h = n-i, f(n) = \sum_{h=1}^{n-i} (h + 1)(h + 2)/2.Следовательно, f(n) = n^3.Это означает, что алгоритмы O(n^3).

Для третьей части вы можете использовать из этого факта, что B[i, j] = B[i, j-1] + A[j].Это означает, что вы можете использовать из предыдущих вычисленных сумм для вычисления переадресованной суммы.Используя этот факт, вы изменяете j - i + 1 на 1.Это означает g(n) = n^2 вместо n^3.

Answer 2

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

Чтобы проанализировать время выполнения, мы можем начать изнутри и постепенно уходить наружу

Add up array entries A[i] through A[j]

Предполагая прямую реализацию, в которой вы зацикливаете записи, это даст вам время выполнения j - i + 1 (абстрактные единицы времени).Точное число будет зависеть от реализации и от того, как вы считаете операции.Для обозначения O(*) это не будет иметь значения.Я сохраню эти конкретные времена и не буду упрощать их до некоторой записи O(*), поскольку вам, вероятно, понадобится определенное время для части (b).

Store the result in B[i,j]

Это время работы 1.Следовательно, деталь внутри внутреннего цикла имеет время работы j - i + 2.Я заменю код на T(j - i + 2) и далее.Итак, код, который мы оставили:

For i=1, 2,...,n
    For j=i+1, i+2, ... n
        T(j - i + 2)
    Endfor
 Endfor

Чтобы найти время выполнения внутреннего цикла, нам нужно вычислить сумму по заданным границам: Sum (for j from i+1 to n) (j - i + 2).Это арифметическая серия с решением 1/2 * (i - n - 5) * (i - n).Код теперь:

For i=1, 2,...,n
    T(1/2 * (i - n - 5) * (i - n))
Endfor

Повторное решение суммы дает нам окончательное время выполнения 1/6 * (n^3 + 6n^2 - 7n).И эта функция в O(n^3).