arrays - 算法的运行时间

Question

抱歉，这是一个由三部分组成的问题。我一直在努力完成第一部分，我认为如果我完成了，其余部分就会到位，但我的运行时间不太合适。我知道有 n 次迭代，但不知道如何在不使用值 j 的情况下计算内循环的迭代次数

考虑以下基本问题。给定一个由 n 个整数 A[1]、A[2]、...A[n] 组成的数组 A。你想输出一个二维的n×n 数组 B，其中 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，在大小为 n 的输入上给出此算法的运行时间的 O(f(n)) 形式的界限(即，数量的界限)算法执行的操作)。

(b) 对于同一个函数 f，证明算法在大小为 n 的输入上的运行时间也是 ~2 (f(n))。 (这显示了 ®(f(n)) 在运行时间上的渐近紧界。)

(c) 虽然你在 (a) 和 (b) 部分分析的算法是最解决问题的自然方法——毕竟，它只是遍历数组 B 的相关条目，为每个条目填充一个值——它包含一些非常不必要的低效率来源。给出一个不同的算法来解决这个问题，具有渐近更好的运行时间。换句话说，您应该设计一个运行时间为 O(g(n)) 的算法，其中 limn-->infinity g(n)/f(n) = O。

Answer 1

我将介绍第一部分。然后，您可能会很清楚地解决第二部分。第三个是一个完全独立的问题(因此，如果您需要帮助，也应该作为一个单独的问题发布)。

分析运行时间，可以从内部开始，逐渐向外

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) 中。