algorithm - 计算算法的 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)。