时间复杂度

什么是大O

算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

我们看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，**所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)**。

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。如图所示：

O(logn)中的log是以什么为底？

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

递归算法的时间复杂度

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

例子：计算x的n次方

最直观的就是用for循环，常规思路：

int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度为O(n)，有没有效率更好的算法呢？

如果是面试场合，不要说：我不会，我不知道了等等。

可以和面试官探讨一下，询问：“可不可以给点提示”。面试官提示：“考虑一下递归算法”。

递归算法思路1：

int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}

我们看一下代码，这里递归了几次？

每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

如果我们想继续降低时间复杂度，再把递归搞一下：

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

这样的时间复杂度是多少？这里用一张图来演示n为16的时候的情况：（举例简单情况）

首先看递归了多少次，n为16的时候，进行了多少次乘法运算呢？

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。

熟悉二叉树话应该知道如何求满二叉树节点数量，这棵满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。

这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示：(m为深度，从0开始，完全二叉树的深度m的求法：log2n-1）

时间复杂度忽略掉常数项-1**之后，这个递归算法的时间复杂度依然是O(n)**。对，你没看错，依然是O(n)的时间复杂度！

那么O(logn)的递归算法应该怎么写呢？

想一想刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢，其实有重复计算的部分。

于是又写出如下递归算法的代码：

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}