如何在这个递归函数上获取时间复杂度(Big-O)

Question

如何获取时间复杂度这个函数？

fun(int n){
     for(int i=0; i<n; i++){
         for(int j=0; j<n; j++){
       print(" ");
       }
     }
    fun(n-3)
}

Answer 1

假设 f（n） 的运行时间为 T（n）。您必须在每个函数调用中循环。所以循环的强制性是 O（n^2）。

f（n） 有 2 个环 （ O（n^2） ） 和一个 f（n-3）。 所以我们得出下面的等式：

T(n) = T(n-3) + O(n^2)

也可以写成：

T(n) = T(n-3) + (n^2)*(1^n)

因此，与上述等式相等的是：(r^3 - 1 )[(r-1)^3]=0

所以我们有r=1 ( 6th degree)所以 T（n） 将是这样的：

T(n) = [a1 + a2*n + a3*n^2 + a4*n^3 + a5*n^4 + a6*n^5 ]*(1^n)

所以最后很明显，对于a1,a2,a3,a4,a4,a5,a6!=0（只能通过 f（n） 的初始值找到），结果是

T(n) = O(n^5) 

Answer 2

递归没有底部，因此它将无限长。由于函数的增长率与输入（n）无关，因此它是一个O（1）函数（无论n有多大，执行时间总是相同的，也就是说，无限）。

如果递归有一个底部，我们可以看到函数在更高的 n 值下增长的速度有多快。每个 n 都会添加另一个通过内部循环的通道，乘以通过外部循环的另一个通道，再乘以递归深度，因此 n*n*n = O（n^3）。

的确，递归的增长速度比两个循环慢一点，但最终它确实与 n 线性增长，这意味着它本身算作 O（n）。