问题描述

时间复杂度问题求解明白

Int fact（int n）
{if （n<=1）
return 1；
return n*fact（n-1）；
}
A. O(log2n) B. O(n） C . (a log2n) D. O(n2)
为什么是B 我不是很明白 n的阶乘按理说不是n(n-1)吗 那么时间复杂度应该是D呀

解决方案

时间复杂度可以简单看成主要工作单元的调用的次数，比如说你题的主要工作单元是：n*fact（n-1），那么实际在整个运行中，调用的次数为 n-1次，那么复杂度取 0（n）。

解决方案二：

for (i =0; i < n; i ++)
{
for(j =0; j < n; j+++)
{..................}
}

这个的复杂度才是N^2

解决方案三：

他只是一个递归，算法的复杂度并没有变

解决方案四：

时间复杂度和主要操作认定有关

递归调用成功的把 主要操作由乘法，转换为函数调用
时间复杂度没变，效率降低了

解决方案五：

 这是尾递归，相当于
while (n > 1)
r = r*n--;
return r;
所以是On