计算程序段时间复杂度：嵌套循环分析

计算程序段时间复杂度：嵌套循环分析

程序段：

i = 0; s = 0;

while (++i <= n) { int p = 1; for (j = 0; j < i; j++) { p *= j; } s = s + p;}

该程序段的时间复杂度为 ( ) 。

A. O(n)

B. O(n*logn)

C. O(nnn)

D. O(n*n)

答案：D. O(n*n)。

解析：

1. 外部循环： while (++i <= n) 循环执行 n 次。

2. 内部循环： for (j = 0; j < i; j++) 的迭代次数随着外部循环变量 i 的变化而变化。 - 当 i = 1 时，内部循环执行 1 次。 - 当 i = 2 时，内部循环执行 2 次。 - ... - 当 i = n 时，内部循环执行 n 次。

3. 总迭代次数： 内部循环的总迭代次数为 1 + 2 + 3 + ... + n，这是一个等差数列求和，结果为 (n*(n+1))/2。

4. 时间复杂度： 由于内部循环的总迭代次数为 O(n^2)，而外部循环执行 n 次，因此整个程序段的时间复杂度为 O(n*n)。