Question

求整数n(n>=0)阶乘的算法如下,其时间复杂度:

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)

Answer 1

#include<stdio.h> 

int main(void) 

{ 

int i,s=1; 

printf("Please input a intdata:"); 

scanf("%d",&i); 

for(;i>1;i--) 

s*=i; 

printf("%d\n",s); 

return 0; 

}

这是一个递归程，可以看出每递归一次n的规模小一，所是结果是线性的。

1、阶乘指从1乘以2乘以3乘以4一直乘到所要求的数。例如所要求的数是4，则阶乘式是1×2×3×4，得到的积是24，24就是4的阶乘。 例如所要求的数是6，则阶乘式是1×2×3×……×6，得到的积是720，720就是6的阶乘。例如所要求的数是n，则阶乘式是1×2×3×……×n，设得到的积是x，x就是n的阶乘。任何大于1的自然数n阶乘表示方法： n!=1×2×3×……×n 　或 n!=n×(n-1)! 　 5！=5*4*3*2*1=120。

2、所要求的数是4，则阶乘式是1×2×3×4，得到的积是24，24就是4的阶乘。 例如所要求的数是6，则阶乘式是1×2×3×……×6，得到的积是720，720就是6的阶乘。例如所要求的数是n，则阶乘式是1×2×3×……×n，设得到的积是x，x就是n的阶乘。在表达阶乘时，就使用“！”来表示。如n阶乘，就表示为n!

Answer 2

B
这是一个递归程，可以看出每递归一次n的规模小一，所是结果是线性的。