解决递归求阶乘问题时间复杂度计算

本问题源于《算法设计分析》，仔细并分析了阶乘问题时间复杂度计算。并为未来设计更好的算法，观测其时间复杂度打下良好的基础。

求n!，n是大于或等于0的整数.

在fac算法中，参数n度量问题的规模，计算结果只不过是O(1)的常数时间。整体fac的时间复杂度递推方程如下: T ( n ) = { O ( 1 ) , n ≤ 1 T ( n − 1 ) + O ( 1 ) , n > 1 T(n)=\left\{ \begin{array}{lcl} O(1),n\le1\\ T(n-1)+O(1),n\gt1\\ \end{array} \right. T(n)={O(1),n≤1T(n−1)+O(1),n>1​

采用迭代法递推: T ( n ) = T ( n − 1 ) + O ( 1 )             = T ( n − 2 ) + 2 O ( 1 )                        = . . . = T ( 1 ) + ( n − 1 ) O ( 1 )                            = O ( 1 ) + ( n − 1 ) O ( 1 ) = O ( n ) T(n)=T(n-1)+O(1)\\ \ \ \ \ \ \ \ \ \ \ \ =T(n-2)+2O(1)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =...=T(1)+(n-1)O(1)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =O(1)+(n-1)O(1)=O(n) T(n)=T(n−1)+O(1)           =T(n−2)+2O(1)                      =...=T(1)+(n−1)O(1)                          =O(1)+(n−1)O(1)=O(n)