求整数n(n≥0)阶乘的算法如下，其时间复杂度是（ ）。

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

复杂度分析

A. $O(\log_2 n)$

B. $O(n)$

C. $O(n\log_2 n)$

D. $O(n^2)$

[tag_link]

正确答案：B

本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是≤1，每调用一次 fact()，传入该层 fact() 的参数值减 1。采用递归式来表示时间复杂度有Tn={O(1),n≤1T(n−1)+1,n>1则T(n)=T(n−1)+1=T(n−2)+2=⋯=T(1)+n−1=O(n)，故时间复杂度为O(n)。