[数据结构与算法]数据结构初步（一）- 时间与空间复杂度

前言

当当当，本节开始进入到数据结构的学习之旅。什么是数据结构呢，什么又是时间复杂度与空间复杂度呢？学习数据结构的道路并不是一帆风顺的，唯有持续冲锋数据结构的高地。

1. 数据结构与算法

1.1 数据结构是啥

数据结构data structure是计算机储存、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

1.2 算法是啥

算法algorithm是一系列的计算步骤，用来将输入数据转换为输出结果。
数据结构与算法是相辅相成的，二者往往同时出现。

2. 算法效率

2.1 如何衡量一个算法的效率

如果给出一个算法，我们如何知道这个算法的效率是怎样的呢？一个程序的源代码简洁，对应的算法效率也会高吗？相同的算法代码在不同机器上的具体执行时间也会有这差别，这取决于机器的新旧。
为了只关注算法本身的效率，而忽略具体环境对算法程序运行造成的影响，前人提出了著名的复杂度方法大O的渐进表示法去衡量一个算法的效率。

2.2 算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间资源也就是内存。
衡量一个算法的效率高低，一般会从时间和空间两个维度出发，引出了时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量一个算法运行时所需要的额外空间。在计算机发展的早期，计算机的容量很小，所以对空间复杂度特别重视，而不那么重视时间复杂度。但是经过计算机行业的迅猛发展，计算机的储存容量有了显著的提升，如今一个算法的空间复杂度不在那么收到人们的关注，而是逐渐重视算法的时间复杂度，毕竟时间就是生命。

3. 时间复杂度

3.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);
}

count共执行了$N^2$次，即函数$F(N)=N^2+2?N+10$
实际计算时间复杂度时，我们不需要计算精确的执行次数，只需要大概执行次数，也就是大O的渐进表示法。

3.2 大O的渐进表示法

大O符号Big O notation：用于描述函数渐进行为的数学符号。
推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中只保留最高阶项；
3. 如果最高阶项存在且最高阶项系数不是1，则去掉与最高阶项相乘的常数系数。
4. 得到大O阶

对于一个与执行次数相关的函数$F(N)=N^2+2?N+10$使用大O阶渐进表示后为$O(N^2)$
为什么我们可以这样去掉函数的一部分项呢？
大O阶表示其实去掉了对函数结果影响不大的项，简洁明了的表示了执行次数。
例子如下表所示：
$F(N)=N^2+2?N+10$

随着N取值的增大，函数实际的执行次数与大O渐进表示后的执行次数逐渐趋于接近，最高项有着决定性的作用(如果有最高项的话)。

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

最坏情况：任意输入规模的最大运行次数上届；
平均情况：任意输入规模的期望输入次数；
最好情况：任意输入规模的最小运行次数下届。

例子：对于在长度为N的数组中顺序查找某个数据x：
最坏情况：N次找到或找不到；
平均情况：N/2找到;
最好情况：1次找到。

在实际情况中一般关注的是算法的最坏运行情况，看的是最坏时间复杂度。本例中为$O(N)$

3.3 例子分析

通过具体的例子来进一步了解时间复杂度。
简单的算法程序可以通过观察代码直接得到时间复杂度；
复杂的算法程序如果我们仅仅通过观察代码得到结果，那么这个结果很可能就是错误的。我们需要逐步的画图分析算法的具体实现步骤，在通过大O阶推导，以此来得到算法的时间复杂度。

计算Func2的时间复杂度

// 计算Func2的时间复杂度
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);
}

执行实际次数的函数$F(N)=2?N+10$
大O阶渐进表示时间复杂度：$O(N)$

计算Func3的时间复杂度

// 计算Func3的时间复杂度
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);
}

执行实际次数的函数$F(N)=M+N$
大O阶推导时间复杂度$O(M+N)$

计算Func4的时间复杂度

// 计算Func4的时间复杂度
void Func4(int N){
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        ++count;
    }
        printf("%d\n", count);
    }

执行实际次数的函数$F(N)=100$
大O阶推导时间复杂度$O(1)$

计算strchr的时间复杂度

// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character );

strchr()函数功能：在一个字符串中顺序查找指定的一个字符并返回这个字符的地址或空指针。
假设该字符串长度时N。

执行实际次数有多种情况：最好1次找到；平均N/2次找到；最坏N次找到或直接找不到。
大O阶推导的时间复杂度(最坏)$O(N)$

计算冒泡排序的时间复杂度

// 计算BubbleSort的时间复杂度
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个元素就是所有元素中的最大的或者最小的。相邻两个元素比较操作进行了N次。
下一趟只需要比较前N-1个元素，者一趟下来本趟中最后一个元素第N-1个元素就是待比较元素中最大的或最小的。相邻两个元素比较操作进行了N-1次。
可以知道最后一趟比较操作了1次。
那么冒泡排序操作共进行了N趟，每一趟比较操作进行了从N开始的递减次数。
即比较操作共进行了$N+(N?1)+...+1=(N?(N+1))/2$次

最坏执行次数（逆序状态）$(N?(N?1))/2$次
最好执行次数（已经是排好序的状态）$N$次
大O阶推导时间复杂度$O(N^2)$

计算二分查找的时间复杂度

// 计算BinarySearch的时间复杂度
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个有序排列的元素的一组数据，查找其中的某个元素x不需要从第一个元素开始寻找，因为这是有序的数据，有着不同于乱序数据的方式。
首先查找有序元素的中间位置的数据，如果中间位置的元素就是要找的元素x就不在继续；否则就继续查找，因为数据是有序的，那么比较中间位置元素与待查找元素x的大小就可以减少一半需要查找的元素：如果中间位置元素大于x，那么就在中间位置左边部分继续查找；如果中间位置元素小于x，那么就在中间位置右边部分继续查找。
每一次查找都在原来基础上缩小一半的查找范围，直到只剩下最后一个元素，此时要么最后一个元素就是要找的x，要么就找不到x。那么总共查找了几次呢？
假设查找了F次，$N/2/2.../2=1$即$2^F=N$可以得到$F=lo{g}_{2}N$

最好执行次数：1次
最坏执行次数：$lo{g}_{2}N$次
大O阶推导时间复杂度：$O(lo{g}_{2}N)$或$O(logN)$
因为对数的底数不好在电脑上打出来，一般简写略去底数，一般$O(lo{g}_{2}N)$表示$O(logN)$

计算阶乘递归的时间复杂度

// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N){
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}

函数调用涉及函数栈帧的创建与销毁过程。
输入一个无符号整数N，第一次调用函数fac(N)，创建fac(N)的函数栈帧；第二次在fac(N)内部调用函数fac(N-1)，创建fac(N-1)的函数栈帧；$...$ 最后第N+1次在函数fac(1)内部调用fac(0),创建fac(0)的函数栈帧。随后从fac(0)开始返回，相应的函数栈帧逐步销毁。
基本操作次数（执行次数）$N+1$次
大O阶推导时间复杂度$O(N)$

计算斐波那契数列递归形式的时间复杂度

// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N){
    if(N < 3)
    return 1;
    return Fib(N-1) + Fib(N-2);
}

函数调用次数共计：$2^0+2^1+2^2+...+2^{N?1}$ =$2^N?1$
大O阶推导时间复杂度$O(2^N)$

4. 空间复杂度

4.1 概念

前面稍微了解了时间复杂度的概念，空间复杂度与时间复杂度类似。

空间复杂度是一个数学函数，对一个算法在运行过程中临时占用储存空间大小的量度。

如同时间复杂度不是计算算法程序运行的具体时间，空间复杂度表示的也不是计算算法程序具体占用了多少字节的空间，而是计算的是算法程序的变量个数**额外空间**。

时间复杂度与空间复杂度有着不同，其中最明显的一个特点是：同一时间不能被程序重复利用，同一块空间能够被程序重复利用。在计算复杂度时需要注意这一个点。

4.2 大O的渐进表示法

大O符号Big O notation：用于描述函数渐进行为的数学符号。
推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中只保留最高阶项；
3. 如果最高阶项存在且最高阶项系数不是1，则去掉与最高阶项相乘的常数系数。
4. 得到大O阶

与时间复杂度的表示形式类似。

4.3 例子分析

计算冒泡排序的空间复杂度

// 计算BubbleSort的时间复杂度
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;
    }
}

程序开辟了3个额外空间：整型变量end、exchange、i，是常数个额外空间。
大O阶推导空间复杂度$O(1)$

计算斐波那契数列的空间复杂度

// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n){
    if(n==0)
        return NULL;
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; ++i){
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
        return fibArray;
    }

斐波那契数列：$1,1,2,3,5,8,13,21，...$
程序开辟了1个long long*类型的栈区空间fibArray、n+1个long long类型的堆区空间、1个int类型的栈区空间，即n+3个额外空间。

大O阶推导时间复杂度$O(N)$

计算阶乘递归的空间复杂度

// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N){
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}

每一次递归函数fac()开辟的空间是常数个$O(1)$，共递归调用开辟函数栈帧了N+1次
则空间复杂度就是$O(N)$

常见复杂度对比

时间复杂度或空间复杂度随元素数量N增加变化的曲线图

结语

本节主要介绍了数据结构入门的概念，着重介绍了时间复杂度与空间内复杂度，我们需要掌握计算一个算法时间复杂度与空间复杂度的方法。现在我们已经踏入了数据结构的大门，开始在数据结构与算法的世界里闯荡！

$END$