关于递归问题的复杂度计算

背景：前段时间在背八股，手撕快速排序，算法时间复杂度为\(O(nlogn)\)，没想太多，记个结论就pass,和当初上算法课的时候一样；然后做小红书笔试题的时候，有一道题是这样:

void func(n){
    if(n==1){
       printf("good\n");
    }
    func(n-1);
    func(n-1);
}

    也是问时间复杂度，当时没多想就选了\(O(n)\)还是什么。今天脑子里忽然就闪过这样一个想法：递归的时间复杂度本质上就是关于递推式的求通项问题。

    先来看最简单的一种递归形式，计算n!的递归代码:

int func(n){
    if(n==1){
         return 1;
    }
    return n*func(n-1);
}

    上面的代码对应的递推式为: \(f(n)=f(n-1)+O(1)\),我们简写为：\(f(n)=f(n-1)+1,f(1)=1\)。这个递推式求通项比较简单：\(f(n)=n\)。func的时间复杂度即\(O(n)\)。

    再说一下小红书那道笔试题，它对应的递推式为：\(f(n)=2f(n-1)+1,f(1)=1\)。这个用高中的那啥凑项技巧就是:\(f(n)+1=2(f(n-1)+1)\) => \(f(n)=2^n-1\)。故func的时间复杂度为\(O(2^n)\)。

    上面的例子都是第n项和第n-1项的递推式，然而我们在写代码的时候很容易碰到第n项和第x项(x!=n-1)的递推式，比如快速排序:

void quicksort(int l,int r){
    if(l<=r){
          return;
    }
    ...  //选取哨兵进行左右两边进行交换的过程，时间复杂度为O(n)

    quicksort(l,index-1);
    quicksort(index+1,r);
}

    在上述代码中，index可能是l~r的任意一个位置。理想情况下index会处于l和r中间，那么有：\(f(n)=2f(n/2)+n\)。

    一看，感觉能求，但是有点麻烦，这时候就该介绍一下主定理了。

    主定理，是分析递归算法时间复杂度的一种重要工具，尤其适用于具有分治结构的递归算法。它适用的递推式如下：

    主定理本身就是递归的形式，是递归方法时间复杂度的一种表示法。T(n) 代表递归方法处理规模为n的数据量的时间复杂度，T(n/b) 代表调用子递归方法的总体时间复杂度，\(O(n^d)\) 代表调用子递归方法这行代码外其他代码（下面简称递归外代码）的时间复杂度。

    当一个递归问题可以表示成上述的递推式的时候，我们有:

    1. 当 \(d < \log_b(a)\) 时，递归时间复杂度为：O(\(n^{\log_b(a)}\))

    2. 当\(d = \log_b(a)\) 时，递归时间复杂度为：O(\(n^d \log n\))

    3. 当\(d > \log_b(a)\) 时，递归时间复杂度为：O(\(n^d\))

    证明思路大家自己去找吧，个人感觉记得结论就行。

    有了主定理后，我们来看理想下的快速排序：\(T(n)=2T(n/2)+O(n)\)。可以得到：a=2,b=2,d=1，有\(d = \log_b(a)\)，对应第2种情况，故时间复杂度为：\(O(n \log n)\)。

    当然，这只是理想的情况，实际上快速排序的时间复杂度应该是index(哨兵位置)取不同值时得到的期望，更加麻烦，最后也是\(O(n \log n)\)。

    这篇博客只是自己的一些想法，写的比较简单，写的过程也有参考一些大佬的博客，比如https://www.cnblogs.com/wind-wound/p/18206958，这一篇就写的比较详细，水平高我太多。