计算算法的 Theta(n)

Question

我正在尝试计算以下算法的 Theta(n)

for i = 1 -> n
   for j = 1 -> n
       B[i,j] = findMax(A,i,j)

findMax(A,i,j)
    if j < i
        return 0
    else
        max = A[i]
        for k = i + 1 -> j
             if max < A[k]
                max = A[k]
        return max

我知道 O、theta 和 omega 大致翻译为

O≈≤

Ω≈≥

Θ ≈ =

对于算法，我认为 omega = n^2，o = n^3，但我不确定 theta 是多少。有什么想法吗？

Answer 1

如果你计算代码行的次数

if max < A[k]

的执行取决于 n 您将获得 Theta(n^3) 次执行。因此，您的算法的运行时间也是 Thetat(n^3)。

Answer 2

Theta(n^3)。嵌套 for 循环有 n^2 次迭代。当 j < i 时，大约一半的迭代运行在 O(1) 时间内完成。这些迭代的另一半对于 j-i 平均有 n/2 差异，因此另一半迭代需要 Theta(n/2) 时间。由于大约一半的 n^2 迭代平均花费 n/2 时间，因此 n^2/2 * n/2 = n^3/4 = Theta(n^3) 时间用于一半的迭代。 n^2 次迭代的另一半需要 n^2/2 = Theta(n^2) 时间。因此总运行time = Theta(n^3)。

计算算法的 Theta(n)

Calculating Theta(n) of an algorithm

algorithm

big-o

big-theta