初阶数据结构与算法——时间复杂度详解

前言

什么是数据结构？

数据结构是计算机存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

这篇文章，我们就先来学习一下时间复杂度和空间复杂度。

1. 算法效率

我们已经了解了什么是算法，那当我们写出一个算法的时候，如何去衡量这个算法的好坏呢？

1.1如何衡量一个算法的好坏

比如，对于下面这个求斐波那契数列的算法：

long long Fib(int N) 
{
    if (N < 3)
        return 1;
    return Fib(N - 1) + Fib(N - 2);
}

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

1.2 算法的复杂度

对于算法的“好坏”，我们一般用复杂度来衡量：

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

1.2 复杂度在校招中的考察

校招的笔试算法题和面试中都会考察对复杂度的计算和理解：

2. 时间复杂度

2.1 时间复杂度的概念

首先我们要知道时间复杂度计算的不是算法的运行时间。

为什么不是运行时间呢？

因为一个算法的运行时间和环境也是有关系的，同一个算法，在不同配置的机器上的运行时间可能就会有很大差异。

时间复杂度的定义：

在计算机科学中，算法的时间复杂度是一个函数（注意这里说的函数不是编程语言中的函数，就是指数学中我们学的函数），它定量描述了该算法的运行时间。

一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。

一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

那到底应该怎么计算呢？我们来看一个实例：

请计算一下Func1中++count语句总共执行了多少次？

void Func1(int N) 
{
    int count = 0;
    for (int i = 0; i < N; ++i) 
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k) 
    {
        ++count;
    }
    int M = 10;
    while (M--) 
    {
        ++count;
    }
    printf("%d\n", count);
}

Func1 执行的基本操作次数 ：

这是它精确的执行次数，那这个就是该算法的时间复杂度嘛？

不是的。

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数。

那么这里我们使用大O的渐进表示法。

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项（其余项对结果影响不大）。

3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

4.实际中一般情况关注的是算法的最坏运行情况

那么在使用大O的渐进表示法以后，Func1的时间复杂度就应该是：

O(n^2)

那为什么是O(n^2)呢？

根据第二条规则，对于运行次数函数

只保留最高阶，舍去其他项。

因为随着N越来越大，我们会发现总的执行次数越来越接近N^2的值，其它项对结果的影响越来越小：

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

总的来说，大O的渐进表示法是对算法执行次数的一个估算，算的是大概的次数所属的一个量级。

2.3 常见时间复杂度计算举例

接下来我们就来一起做一些例题，练习一下。

例1双重循环

void Func2(int N) 
{
    int count = 0;
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

大家思考一下这个算法的时间复杂度应该是多少？

答案是O(N)。

怎么算的呢？

首先准确的执行次数很容易算出来是2n+10，那10 直接就可以去掉了，随着n越来越大，10对结果的影响就越来越小了，加不加都无所谓了。

那为啥不是2n呢？

这就对应了规则3，如果最高阶项存在且不是1，则去除与这个项相乘的常数。

就算是100，1万也要去掉。

所以最终答案是O(N)。

例2. 多未知数

void Func3(int N, int M) 
{
    int count = 0;
    for (int k = 0; k < M; ++k)
    {
        ++count;
    }
    for (int k = 0; k < N; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

这个时间复杂度又是多少呢？

是O(M+N) 。

准确的执行次数就是M+N，都是未知数，没有什么可以省去的项，所以就是O(M+N) 。

例3. 常数次循环

void Func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

O(1)

总共执行了100次，是常数次。

这就对应了第一条：用常数1取代运行时间中的所有加法常数。

也就是说，只要一个算法的执行次数是常数次，不管多大，都是O(1)，当然执行常数次的算法，这个常数，一般也不会特别大。

例4. strchr

const char* strchr(const char* str, int character);

大家计算一下这个函数的时间复杂度是多少？

先给大家介绍一下这个函数吧。

这是一个库函数：

它就是在一个字符串中去查找一个字符，如果找到，返回该字符的地址，如果找不到，返回空指针。

那它的时间复杂度应该怎么算呢？

比如说，现在有这样一个字符串：

"abcdefgtioevdksjdx"

我们现在借助strchr来查找其中的一个字符，那会有一个问题：

就是如果我们找的字符是a，那上去一下就找到了，如果找的是x，那是不是要遍历到最后一个字符才能找到，假设是第N个。这是最好和最坏的情况，那当然还会有平均情况。

所以：

有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况。

所以数组中搜索数据时间复杂度为O(N)

那strchr的时间复杂度就也是O(N)了。

例5. 冒泡排序

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

冒泡排序，相信大家应该都知道这个算法吧，它的时间复杂度又是多少呢？

我们来分析一下，冒泡排序就是两两比较嘛，比如升序的话就是前面比后面大，就交换。

假设N个数，就需要比较N-1趟，每趟比较的次数依次减1（因为每比一趟，就有一个数会交换到最终应该在的位置）。

那准确的次数就是N-1+N-2+...2+1.

是个等差数列，求和是N*（N-1）/2=1/2*N^2-1/2*N

那按照大O的渐进表示法，只保留最高阶，去掉常数系数，就是O(N^2)

有时候我们不用看代码，根据算法的思想就能计算出时间复杂度。

例6. 二分查找

再来看一个。二分查找：

int BinarySearch(int* a, int n, int x) {
    assert(a);
    int begin = 0;
    int end = n - 1;
    // [begin, end]：begin和end是左闭右闭区间，因此有=号
    while (begin <= end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

二分查找其实每次都取中间值和我们要查找的值比，这样每次查找的范围就缩到原来的一半，最坏的情况就是一直缩小，一直缩小，直到就剩最后一个数字，如果是，就找到了，如果不是，就说明找不到。

假设有N个数，查找依次，范围就除2，最坏的情况就是一直除到等于1。

所以结果是log2N。

另外，时间复杂度的计算中log2N可以简写成logN。

例7. 递归求阶乘

long long Fac(size_t N) {
    if (1 == N)
        return 1;
    return Fac(N - 1) * N;
}

是一个递归，求阶乘的递归。

递归调用了几次呢？

是不是N次啊，Fac(N )要调用Fac(N - 1) ，Fac (N - 1)再调用Fac(N - 2) ，以此类推，直到Fac(1)结束。

那每次递归有几次运算呢？

return 的时候有个相乘运算，就算加上if判断也就两次，那就是2N次。

那根据大O的渐进表示法吧常数系数2去掉，不就是O(N)嘛。

那现在我们对这个算法做一点改动，变成这样：

long long Fac(size_t N) {
    if (1 == N)
        return 1;
    for (int i = 0; i < N; i++)
    {
        ;
    }
    return Fac(N - 1) * N;
}

这次它的时间复杂度又是多少？

我们看到这次多了一个for循环，循环N次，当然每次递归N会减1，第一次是N次（if判断和return的相乘我们就不加了，这个不影响的，而且时间按复杂度最终算的就是一个大概执行次数，当然你加上也没问题，建议这一块有时候不要考虑那么细致，有时反而会因此想不明白），那第二次N-1，然后N-2，…直到N=1，开始返回。

那总的次数其实就是一个等差数列：

N N-1 N-2 ... 3 2 1

求和就是N*（N+1）/2，那只保留最高阶，去掉系数，就是O(N^2)

所以，对于递归函数的时间复杂度的计算：

我们要算的就是每次递归调用的执行次数的累加，当然，得出的结果需要我们使用大O的渐进表示法再去简化。

例8. 递归求斐波那契第N项

long long Fib(size_t N) {
    if (N < 3)
        return 1;

    return Fib(N - 1) + Fib(N - 2);
}

这个算法的时间复杂度时多少呢？

是O(2^N)

我们一起来分析一下：

Fib(N)会递归调用Fib(N - 1) 和 Fib (N - 2) ，Fib (N - 1) 又调用Fib (N - 2)和 Fib (N - 3) ， Fib (N - 2)调用Fib (N - 3)和 Fib (N - 4)，以此类推，每个分支直到 N < 3开始返回：

最终结果是O(2^N)