算法的时间复杂度是怎么度量的？

Question

每次问时间复杂度多少都蒙蔽，到底怎么算的？

Answer 1

时间复杂度是指某个算法在最坏的情况下的运算时间。比如使用的遍历法查找一组数据中的某1个。

数组：1 2 3 4 5 6 7

此时若查找1，需要比较1次；查5需要比较5次；查7则需要比较7次。而这个7则是最坏情况。所以遍历法进行查找时，如果数组的长度为N，则时间复杂度为N。表示在最坏的情况下需要经过N次查找。

Answer 2

时间复杂度先有一个假设：假设只有循环结构耗时、且执行时间均等。

然后就是公式：T(n) = O(t(n))，其中 n 表示多少次循环、t(n) 表示每次循环耗时、T(n) 就是时间复杂度。

另外再一点就是说，某些算法可能在循环结构中有判断条件、当满足条件时就跳出循环了，这种情况下算法的时间复杂度按最极端最坏的情况考虑，也就是假设只有循环到最后一次才满足条件跳出。

---

时间复杂度是 O(1) 的例子：

int i = 0;
i++;

没有循环结构（或者说循环次数为 1），也就是说整体耗时不会随着某个变量的增大而增长。

---

时间复杂度是 O(n) 的例子：

int j = 0;
for (i = 0; i < n; i++)
{
   j += i;
}

循环 n 次，即整体耗时是随着 n 的增大而增长。

---

时间复杂度是 O(log n) 的例子：

int i = 0;
while (i < n)
{
    i = i * 2;
}

循环 log 2^n 次。

---

时间复杂度是 O(n²) 的例子：

int k = 0;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        k++;
    }
}

嵌套循环，总共循环 n^2 次。

---

还有很多，不一一列举了，会算就行。

Answer 3

我们一般说的时间复杂度，大家应该默认都是平均时间复杂度。

时间复杂度分为三种：最差、平均和最佳。

对于如何求一个算法或一个函数的复杂度，上面的回答已经很清楚了。如果只有 while、for、if 这类简单的语句，复杂度其实非常好求。但我还是要举个例子来说下，比如下面的伪代码，

void func(array)
{
    int len = array.length;
    for (int i = 0; i < len; ++i)
    {
        if (array[i] > 10)
            return;
        else
            array[i] = 0;
    }
}

如果别人直接问我：“这个函数的时间复杂度是多少？”，我会直接说：“O(n)”。如果接着问我：“那么它的最差和最佳时间复杂度呢？”，我会说：“最差 O(n) ，最佳 O(1)”。

那么最差和最佳是怎么算的？

先来看最差。如果这个数组的值都小于 10，那这个 for 循环一定会全部遍历完，O(n) 最差没毛病，就这么简单。

那最佳呢？我们再想一下，如果这个数组的第一个元素的值就大于 10 呢？那么整个函数立即退出，时间复杂度只有 O(1)。

最差和最佳需要根据具体的数据集来分析，没什么难理解的。难的的是平均复杂度。

从这个平均的字眼，我想你应该是明白它的含义，但关键怎么算？抱歉，我不会。这涉及到概率论和当前数据集的产生背景来综合考虑。

举个例子，如果这个数组是某个幼儿园所有大班班级的学生年龄，那么你猜猜它的平均复杂度近似于多少？很好猜，肯定是 O(n)。为什么？你见过几个念幼儿园大班的孩子年龄已经到 10 岁以上的。但如果我告诉你这个数据来自所有高三班级的学生的年龄，那么复杂度近似于多少呢？同理，肯定是O(1)，理由我就不多说了。但是如果我告诉你这个数组的数据就是随机的，非常非常随机，那么怎么求？鉴于我的概率论没学好，我就不吹逼了，我也不会。

总之呢，一个知名的算法的平均复杂度一般都有大牛帮我们算好了，直接吃现成的就行。而最差和最佳没什么难度，还是需要掌握的。

最后再来看看一些复杂的函数或算法的时间复杂度怎么求？这个复杂函数一般都是指含有递归的函数。举个例子，

void func(array, length)
{
    if (length == 0 || length == 1)
        return;
        
    int half = length / 2;
    
    for (int i = 0; i < half; ++i) // 做一半
    {
        array[i] = 0;
    }
    
    func(array, half); // 少一半
}

递归的求解其实很简单。我们假设 func 的时间复杂度是 T(n)。那么 T(n) = n/2 + T(n/2)。

这个很好理解吧，n/2 对应那个 for 循环，T(n/2) 对应底部的 func(array, half)。剩下的就是高中数列了，把 T(n) 解出来，是多少那就是多少。

你可以再看下快排的最差和最佳的计算，见 https://subetter.com/algorith...。

另外这个 https://ethsonliu.com/2018/04... 是应对所有递归函数的计算公式和方法。读起来可能不太好读，当时写的太着急，说了很多人类听不懂的，再找时间改下吧，现在就将就着看吧。

Answer 4

题主可以看看MIT的算法导论公开课前几节，一直在教你怎么求复杂度