以下程序段的时间复杂度是多少，为什么？

Question

如题所述

Answer 1

可以使用迭代法来求解。假设求n时复杂度为T(n)。可见算法的递归方程为： T(n) = T(n - 1) + O(1); //这是因为求fact(n)，需要先计算出fact(n-1) （复杂度为T(n-1)），再与n相乘（这部计算复杂度为O(1)）
迭代展开： T(n) = T(n - 1) + O(1)
= T(n - 2) + O(1) + O(1)
= T(n - 3) + O(1) + O(1) + O(1) //因为T(1)也为O(1)
= ......
= O(1) + ... + O(1) + O(1) + O(1)
= n * O(1)
= O(n)追问

最后那个return(n*fact(n-1))这里，是怎么理解的？这难道不是n的值变大了么，成了n(n-1)了？这个时间复杂度不应该n!么？

追答

假设计算fact(n)复杂度为T(n)，那么同理计算fact(n-1)为T(n-1)。用T(n-1)的时间计算出fact(n-1)后，需要多少时间计算fact(n)呢？O(1)的时间。因为只要n乘以计算出的fact(n-1)的值即可。
所以T(n) = T(n-1) + O(1)。

追问

现在发现是我自己理解错了。return(n*fact(n-1))这一步时间复杂度也应该是O(1)，不过需要执行n次。是这样的吗？

追答

是的。

追问

哦哦。感谢。

本回答被提问者采纳