以下程序的时间复杂度

Question

algorithm what (n)      
begin 
    if n = 1 then call A 
    else 
        begin
            what (n-1);
            call B(n)
        end
end.

在上面的程序中，我被要求找出过程 A 花费 O(1) 时间而过程 B 花费 O(1/n) 的时间复杂度。

我形成了递归关系T(n) = T(n-1) + O(1/n)

然后解决它，我得到了 T(n) = O(log n) 因为如果我们使用回代法求解它，我们将得到调和级数，时间复杂度来计算调和级数的总和是 O(lgn ).但答案是 O(n)。我无法弄清楚他们是如何得到这个答案的。在解释中，他们在递归关系中添加了一个常数乘以 n。我不明白为什么我们应该加上那个常数倍 n。请帮助我理解这一点。

Answer 1

这很可能是作者/考官为了让你出局而设置的诡计题。您必须注意，每次调用 what 时涉及的 O(1) 操作（将参数压入堆栈等）掩盖了 B 的 O(1/n) 复杂性——至少 渐近 说。所以实际时间复杂度是T(n) = T(n - 1) + O(1)，给出了正确答案。