前言

说到时间复杂度，作为程序员或多或少都会有所接触，特别是算法工程师肯定是天天和这个概念打交道，其实前几篇总结排序的文章我一直没有提时间复杂度，因为网上太多的文章讲这个概念了，所以我只总结了一下我对几种排序算法的理解，以及简单的实现代码，而当我今天准备总结一下快速排序的时候，我发现各个关于快速排序的文章都有讲到时间复杂度，有的甚至直接就给出 O(N*log(N))，这个对数是以2为底的，还是以10为底的都没有说清楚，这简直让人感到莫名其妙，所以我决定还是简单说一下我对时间复杂度这个概念的理解。

其实时间复杂的作用很简单，就是用来表示算法运行时间与数据规模的关系，其中的数据规模常常用字母N或者n表示，将算法的运行时间表示为n的函数表达式应该为 t=f(n) ，而时间复杂度就是表达式中幂最高的那一项，然后去掉常数系数，比如当算法运行时间表达式为 t = f(n) = 3 * n^2 + n 时，那么这个算法的时间复杂度就是O(n^2)，字母O用来表示时间复杂度，也就是该算法与数据规模成平方阶的关系，为什么要去掉一次项n，因为在数据规模扩大时，它相对于平方阶来说基本可以忽略不计。

时间复杂度计算方法

虽然很多编程工作者都接触过时间复杂度，但是真正要想把时间复杂度算明白可不是件容易的事，特别是遇到时间复杂度中包含对数项的，那就更让人糊涂了，很多人搞不明白为什么会有对数次的运算，实际上二分法常常是导致时间复杂度中出现对数项的一种算法，要算出时间复杂度，本质上就是算出执行完算法算所需要的操作次数，这种操作通常是比较、赋值、交换等等，而时间复杂度与数据规模相关，通常把一个算法执行完所需的操作次数，表示成和数据规模n相关的函数，这就是我们所说的时间复杂度。
时间复杂度是用来衡量算法所需时间资源的，所以只保留最高次幂的项就可以，不用纠结于是O(n^2+n)还是O(n^2)，在大规模的数据面前，这两种时间复杂度几乎相等，总之一句话，看一个算法的时间复杂度，就是数这个算法执行完所需要的操作次数，并且把这个次数表示成与n相关的简单函数。

时间复杂度示例

接下来我们举几个简单的例子，来理解一下什么是时间复杂度，并且了解一下“计算时间复杂度就是数算法执行操作的次数”这句话的意思，接下来我们一起数一下：

常规方法计算区间[1,n]中所有整数的和
1
2
3
4
5
int sum = 0, n = 10000;
for (int i = 1; i <= n; i++)
{
sum += i;
}
上述代码就是一个很简单的计算方法，具体操作就是遍历区间[1,n]内的所有整，然后依次相加，执行次数很好数吧？就是n次，因为每遍历一个数，就会执行一次累加操作，一共有n个数字，所以执行完这段代码需要进行n次累加运算，随着数据规模的扩大，也就是数字n的扩大，计算次数也在扩大，但是还是n次，所以可以用n来表示这段代码的时间复杂度，也就是O(n)。
利用等差数列公式计算区间[1,n]中所有整数的和
1
2
int n = 10000;
int sum = (1 + n) * n / 2;
等差数列的求和公式相信很多人都是知道的，那么这种计算方法对于遍历来说快了太多，因为它是直接计算出来的，也就是1次就能计算出结果，计算次数不会随着数据规模的扩大而扩大，那么这个算法的时间复杂度就是O(1)，也许有的人会纠结这里有加法、乘法、除法，不应该是3次运算吗？实际上就是3次运算，但是常数级的时间复杂度都会用O(1)来表示，它是一个衡量的指标，不需要精确到具体的次数，即使这个常数次数是1000也写成O(1)即可，所以通过这点可以看出，时间复杂度是O(1)的算法未必就比时间复杂度是O(n)的算法计算次数少，比如这个例子中，当n小于3时，第一种算法反而计算的次数少，但是时间复杂度通常是用来衡量数据规模很大的时候，算法所需时间的情况，所以通常情况下O(1)的算法在时间上还是优于O(n)的算法。

利用冒泡排序对所给数组进行排序

void bubble_sort(int array[], int n)
{
    for (int bubble_count = 0; bubble_count < n - 1; ++bubble_count)
    {
        for (int bubble_pos = 0; bubble_pos < n - 1 - bubble_count; ++bubble_pos)
        {
            if (array[bubble_pos] > array[bubble_pos + 1])
            {
                swap_data(&array[bubble_pos], &array[bubble_pos + 1]);  // 交换数据
            }
        }
    }
}

冒泡排序算是排序算法中规则比较简单的了，那么它的时间复杂度怎样来计算呢，或者说怎样来数它的执行次数呢，本例的执行操作次数指的是比较和交换，随着数据规模的扩大，也就只有这些操作次数是跟着变的，那么我们来数一数执行这些操作的次数，首先这是个双重循环，外层循环会遍历n-1次，随着外层循环增多内层循环次数会逐渐减少，听起来很麻烦的，外层和内层都在变化，怎么计算呢？其实可以回归本质，我们看看一共执行了多少次比较运算就可以，第一遍冒泡，内层循环执行了n-1次比较，第二遍冒泡，内层循环执行了n-2次比较，依次类推最后肯定是执行了1次比较，一共比较了多少次是不是就很好计算了，这些次数就是一个等差数列，求和就是这个算法的执行次数，f(n) = (1 + n - 1) * (n - 1) / 2 = n * (n - 1) / 2 = n^2 / 2 - n /2，根据时间复杂度定义，取最高次幂的项去掉系数就得到冒泡排序的时间复杂度O(n^2)。

计算一个十进制数的所有位上（个位、十位、百位…）上1的个数，例如12341这个数中包含2个1
1
2
3
4
5
6
7
8
9
10
11
12
int count_one(int n)
{
int count = 0;
while(n > 0)
{
if ((n % 10) == 1)
++count;

n /= 10;
}
return count;
}
这也是一个很简单的算法，我们只要取出每一位上的数字，看看是不是1就可以，如果是1的话统计的变量count就加1就可以，那么这个算法的操作次数与数据规模n有什么关系呢，实际上这次数我们很清楚，就是n一共有几位数，就需要执行几次操作，当数字是34时，我们需要执行两次操作，当数字是24353的时候我们需要执行5次操作，那么怎么把这个次数表示成n的函数呢，仔细想想者原来就是对数，在本例中f(n) = (int)lg(n) + 1，也就是对n取10的对数，然后取整后加1，那么这个算法的时间复杂度就出来了，就是去掉常数项和修饰符变为O(lg(n))。

总结

写这篇总结的初衷就是网上太多的算法直接给出了时间复杂度，而缺乏必要的说明，其实时间复杂度的计算并不算太复杂，只要你回归定义的本质，仔细的算算究竟需要多少次操作就可以得到大概的时间复杂度，并且一个算法的时间复杂度也不是固定的，比如快速排序，一般大家都喜欢说它是N乘以对数级的，但是当它的最坏情况发生时，它会退化成平方级的。