编写递归函数 计算n!。要求n值从主函数输入 n为正整数。
已帮助 人
回答
共1条回复-
用基本运算乘法的运算次数作为衡量时间复杂度的量当n=0时，程序执行if(n==0) return 1;,并没有做乘法，故T(0)=0;当n>=1时程序执行n*Func(n-1);此时T(n)= T(n-1)+1故: 替换法: T(0)=0,T(1)=1,T(2)=2-----总结得到:T(n)=n;归纳法证明:(1),当n=0时,T(0)=0,结论成立;(2)假设当k所以，对所有n>=0有T(n)=n;成立.迭代法:T(n)=T(n-1)+1=(T(n-2)+1)+1=((T(n-3)+1)+1)+1=....=T(0)+1+1......+1(n个1)=n