递归算法的最佳案例分析

Question

我被问到以下问题：

给出了以下算法：

函数f1(a，b) // a: int // b:如果b == 0返回b，则返回a+ f1(a，b-1)

确定该算法的最佳和最坏情况复杂度。

我用O(n)和Ω(1)回答

当O(n)

• But和a ∈ Z时，每次将b减少1 (T(n) = 1 + T(n-1))，这意味着当a -> ∞和b = 0时，总是立即返回基本情况，因此是Ω(1)

。

但答案是：

O(n)和Ω(n)

为何会这样呢？

n被假定为b，而Ω(1)只是Ω(n)，因为n = 0

Answer 1

例1:当b -> ∞和a ∈ Z时，肤色将是O(n)和Ω(1)

案例2:对于a -> ∞和b = 0，复杂性将是O(1)和Ω(n)

因此，考虑到这两种情况，最好的情况复杂性是O(n)，最坏的情况是Ω(n)。