简单伪代码函数的渐近复杂度

Question

我想了解如何推导出此函数的渐近运行次。

输入：包含n个整数A[1]到A[n]的数组A 输出：二维 n×n 数组 B 其中 B[i,j] for i

$ \sum_{k=i}^j A[k] = A[i] + A[i+1] + ... A[j] $

我尝试计算每行伪代码的运行次

for i=1 to n                                     O(n)
    for j=i to n                                 O(n^2)
        add up array entries A[i] through A[j]   O(n^3) ??
        store result in b[i,j]                   O(n^2)
return B

所以总运行时间是 $O(n^3)$ 我还需要根据 big-$ \omega $

计算复杂度

Answer 1

你如何实施很重要 add up array entries A[i] through A[j]:

for i = 1 to n
    for j = i to n
        sum = 0
        for k = i to j
            sum = sum + A[i]
        b[i,j] = sum
return b

以上是 O(n^3) 和 Omega(n^3) 因此 Theta(n^3)。但是，如果您以不同的方式计算 sum：

for i = 1 to n
    sum = 0
    for j = i to n
        sum = sum + A[i]
        b[i,j] = sum
return b

这是 O(n^2)、Omega(n^2) 和 Theta(n^2)。对于您的具体问题 - 如果您在基于简单代码的问题中进行运行时分析，O 和 Omega 通常是相同的（也就是说，您通常会获得 Theta 边界）。 Theta 边界是查看特定实现时的规则，而不是例外。

简单伪代码函数的渐近复杂度

Asymptotic complexity of a simple pseudocode function

complexity-theory