初阶数据结构--复杂度
第一讲 复杂度
1. 数据结构前言
从本文开始数据结构与算法的学习，在计算机中有很多各种各样的数据，而这些数据是杂乱无章的，但是为了更好地存放和使用这些数据需要对这些数据进行管理就引入了数据结构这个概念，数据结构就像是储存这些数据的容器。当程序员需要对某些数据进行增删查改，就可以在这个结构里对数据进行管理。
数据结构的定义：
数据结构是计算机存储，组织数据的形式，指相互之间存在一种或者多种特定关系的数据的集合。
数据结构包括：线性表、树、图、哈希等。
然而常说的数据结构与算法中的算法又是什么呢？上文说了由于引入了数据结构这个概念，程序员将数据放在数据结构这个“容器”中，但是在使用的时候需要将这些数据拿出，那么将这些数据拿出来的过程叫做算法。
算法的定义：
算法就是定义良好的计算过程。简单来说算法就是一系列的计算步骤，用来将数据转成输出结果。
2.算法的效率
既然算法是一系列的计算步骤，那么就一定有好的计算步骤差的计算步骤之分，下面通过一个案例代码感受一下。
案例：旋转数组https://leetcode.cn/problems/rotate-array/description/
思路：
先将数组中的最后一位保存下来
- 将数组整体向右移动一位
- 数组中的最后一个数据挪到第一位
- 将上述过程循环K次
void rotate(int* nums, int numsSize, int k)
{
while(k--)
{
int end = nums[numsSize - 1];//保存最后一位
for (int i = 0; i < numsSize; i++)
{
num[i + 1] = num[i];//数组整体右移一位
}
num[0] = end;//将数组最后一位放到第一位
}
}
代码点击执行可以通过，但是当我们点击提交之后却显示超出时间限制，点开发现最后第38组数据没有通过检测，可以看到这一组中的数据极其庞大，也就导致了最后程序执行的时候时间过长从而超出时间限制。
从而可以看出这个算法并不是那么高效完美的，所以为了提高算法的效率，引入了一个可以相对量化的指标也就是复杂度来衡量一个算法的好坏。
2.1 复杂度
复杂度的概念：
算法在编写成可执行程序之后，运行需要消耗计算机的时间资源和空间（内存）资源。因此**衡量一个算法的好坏，一般是从时间和空间这两个维度来衡量，**即时间复杂度和空间复杂度。
- **时间复杂度：**主要衡量一个算法运行的快慢。
- **空间复杂度：**主要衡量一个算法运行所需要的额外空间。
因为在计算机发展早期，计算机的存储容量很小，所以对于空间复杂度很在乎。但是随着计算机行业的迅速发展，现在计算机的存储容量已经大幅提高，所以如今已经不是很关注一个算法的空间复杂度。所以下面先进行时间复杂度的介绍。
2.1.1 时间复杂度
因为时间复杂度与时间有着密切关系所以写了下面的代码用于显示语句的运行时间：
//代码1
#include <stdio.h>
#include <time.h>
int main()
{
//得到算法开始时间
int begin = clock();//clock函数返回当前语句执行时的时间，单位是ms
int count = 0;
for (int i = 0; i < 10000000; i++)
{
count++;
}
///
//得到算法结束时间
int end = clock();
printf("time: %d\n", end - begin);
return 0;
}
运行结果：
time：0
- 可以看出计算机的执行速度是很快的，所以下面需要继续增加循环的次数到1亿，达到增长时间的目的。
- 同时改变程序的编译环境，配置为
Debug x86环境下，编译这段代码。
//代码2
#include <stdio.h>
#include <time.h>
int main()
{
//得到算法开始时间
int begin = clock();
int count = 0;
for (int i = 0; i < 100000000; i++)
{
count++;
}
///
//得到算法结束时间
int end = clock();
printf("time: %d\n", end - begin);
return 0;
}
运行结果：
time：70
此时就可以显示出这段算法所消耗的时间了，但是此时还存在一些问题：
- 如果继续多运行几次可以发现程序每次的时间并不固定，有时为71、73等。
- 改变环境为
Debug x64，又会发现此时的时间为61、62等。
出现了以上现象后，可以想到用一个定量的数据去衡量一个算法的时间复杂度是不现实的，可以总结为以几点原因：
因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译 器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
所以在计算机科学中，算法的时间复杂度是一个函数式T(N)，它描述了算法的运行时间。那么函数是T(N)又是什么呢？
- 这个函数计算了程序的执行次数。
- 因为编译后的算法会生成二进制指令，程序的运行也就是CPU执行这些二进制指令。那么就可以通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样（实际中有差别，但是微乎其微），那么算出来的执行次数就是一个与运行时间呈正比例的量。
- 这种方法就不会因为具体的编译环境、运行环境的不同，而造成出现了不同的时间复杂度。
- 同时执行的次数代表了算法时间效率的优劣，这种方法也可以避免只有在程序运行之后才可以知道算法的消耗时间，可以在看到代码时候就可以知道这个算法的时间复杂度，也就可以在运行之前就可以比较出两个算法的好坏。
上面介绍了时间复杂度的相关概念，下面通过具体的代码示例深刻的理解时间复杂度。
2.1.1.1 案例一（大O渐进表示法的应用1）
// 案例代码1
// 请计算⼀下Func1中++count语句总共执⾏了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
} //N*N
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
} //2N
int M = 10;
while (M--)
{
++count;
} //10
}
**分析：**Func1执⾏的基本操作次数：
T ( N ) = N 2 + 2 ∗ N + 10 T (N) = N^2 + 2 ∗ N + 10 T(N)=N2+2∗N+10
| N | T(N) |
|---|---|
| N=10 | T(N)=130 |
| N=100 | T(N)=10210 |
| N =1000 | T(N)=1002010 |
通过对N取值分析，对结果影响最⼤的⼀项是 N 2 N^2 N2，所以也可以对T(N)粗估写成T(N) = N 2 N^2 N2。
**（重点）**之所以可以采用这种粗估的方式改写T(N)的原因如下：
实际中在计算时间复杂度时,计算的也不是程序的精确的执行次数,精确执行次数计算起来还是很麻烦的（不同的一句程序代码,编译出的指令条数都是不一样的），计算出精确的执行次数意义也不大，因为计算时间复杂度只是想比较算法程序的增长量级，也就是是当N不断变大时T(N)的差别，上面已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以只需要计算程序能代表增长量级的大概执行次数即可。
复杂度的表示通常使用大0的渐进表示法。
2.1.1.2 大O渐进表示法（重点）
大0符号(Big O notation)：是用于描述函数渐进行为的数学符号。
推导大O阶规则：
- 时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时,低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。
- 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。
- T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。
经过上面的介绍之后，用大O表示法去除低阶项，则案例一中的时间复杂度就是O( N 2 N^2 N2)。
2.1.1.3 案例二（大O渐进表示法的应用2）
// 案例代码2
// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
} //2N
int M = 10;
while (M--)
{
++count;
} //10
printf("%d\n", count);
}
分析：
Func2的执行的基本操作次数：T(N) = 2N + 10
根据大O渐进表示法的规则去除低阶项和最高项项目系数，此时的时间复杂度为O(N)。
2.1.1.4 案例三（含多个未知循环次数）
// 案例代码3
// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
} //M
for (int k = 0; k < N ; ++ k)
{
++count;
} //N
printf("%d\n", count);
}
分析：
这里在可以很轻松的写出T(N) = M + N，但是由于M与N之间的数量级关系并不明确，所以在根据大O渐进表示法的规则的时候，并不知道怎样进行低阶项的去除。
- 所以这里即可以写成O(M + N)
- 也可以对M和N进行分类讨论：
- 若M >> N，O(M)
- 若M << N，O(N)
- 若M == N或者数量级相似，O(M + N)
2.1.1.5 案例四（循环常数次）
// 案例代码4
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
} //100
printf("%d\n", count);
}
分析：
根据循环写出时间复杂度函数式T(N) = 100，在根据大O渐进表示法的规则3，可以写出时间复杂度O(1)。
2.1.1.6 案例五（多情况讨论）
// 案例代码5
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
分析：
strchr是一个用于在一串字符串中寻找character这个字符，如果找到则返回下标，如果没有找到则返回NULL的函数。
因为这里函数的执行会遇到不同的好几种情况，这些情况也分别对应不同的时间复杂度，所以需要分类讨论分别将这几种情况的时间复杂度都写出来。
- **最好情况：**查找的数组在字符串前部（循环次数较少可控），则：T(N) = 1 O(N) = 1
- **最坏情况：**查找的字符在字符串后部（循环次数没法估计），则：T(N) = N O(N) = N
- **平均情况：**查找中的字符在字符串中间部分（处于以上两种情况之间），则：T(N) = N/2 O(N) = N
面对三种不同情况中的两个不同的时间复杂度，可以发现有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数（上界）
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数（下界）
大O的渐进表示法在实际中⼀般情况关注的是算法的上界，也就是最坏运行情况。
所以根据上述介绍，最坏的情况O(N) = N为此题答案。
2.1.1.7 案例六（冒泡排序）
// 案例代码6（冒泡排序）
// 计算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;
}
}
补充：冒泡排序的介绍
复杂度分析：
此题仍然因为排序存在多种情况，所以需要分情况讨论写出不同情况的时间复杂度。
- **若数组已经为正序数组：**不进入内层的交换位置循环，直接遍历数组即可，则：T(N) = N
- **若数组有序且为降序数组：**最复杂的情况，需要将内外层循环走满，则：T(N) = N ∗ ( N + 1 ) / 2 N*(N+1)/2 N∗(N+1)/2 = N 2 / 2 + N / 2 N^2/2+N/2 N2/2+N/2
综上根据大O渐进表示法，BlubbleSort的时间复杂度取最差的情况为： O ( N 2 ) O(N^2) O(N2)。
2.1.1.8 案例七（复杂度中引入对数）
// 案例代码7
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
分析：
- 当n=2时，执⾏次数为1
- 当n=4时，执⾏次数为2
- 当n=16时，执⾏次数为4
- 假设执⾏次数为x ，则 2 x = n 2^x = n 2x=n ，因此执⾏次数： x = l o g n x = log n x=logn
因此：func5的时间复杂度取最差情况为： O ( l o g 2 n ) O(log₂ n) O(log2n)，写作 O ( l o g n ) O(log n) O(logn)
注意书籍中 l o g 2 n log₂ n log2n 、 l o g n log n logn 、 l g n lg n lgn 的表示
当n接近⽆穷大时，底数的大小对结果影响不大。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表示为 l o g n log n logn
不同书籍的表示方式不同，以上写法差别不⼤，这里建议使⽤ l o g n log n logn
2.1.1.9 案例八（有关递归的复杂度计算）
// 案例代码8
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
分析：
递归过程：
递归N次，每一次的时间复杂度都是O(1)，加在一起这个递归的时间复杂度为O(N)。
递归的时间复杂度：
单词递归的时间复杂度 * 递归次数
2.1.2 空间复杂度
虽然前文说了现在计算机发展十分迅速，计算机的存储容量大幅提高，对于空间复杂度的关注度也逐渐降低，但是在平时的开发过程中，作为程序员仍不可以肆意的浪费空间，合理的使用空间，对空间复杂度有着清晰的认知也是十分重要的。
空间复杂度的介绍：
- 空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。
- 空间复杂度不是程序占用了多少bytes的空间,因为常规情况每个对象;大小差异不会很大,所以空间复杂度算的是变量的个数。
- 空间复杂度计算规则基本跟时间复杂度类似，也使用大0渐进表示法。
- 注意：函数运行时所需要的栈空间（存储参数、局部变量、一些客存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
2.1.2.1 案例一（了解空间复杂度）
// 案例代码1
// 计算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;
}
}
分析：
因为函数栈帧在编译期间已经创建好了，只需要关注函数运行时额外申请的空间即可。
BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个外空间，根据大O渐进表示法，将所以常数表达式的复杂度都写做常数1。
因此空间复杂度为O(1)。
2.1.2.2 案例二（递归的空间复杂度）
// 案例代码2
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
分析：
Fac递归调用了N次，每次调用都会开辟一个函数栈帧，所以一共开辟了N个函数栈帧。
因此空间复杂度为O(N)。
2.1.3 常见复杂度的对比
在这里插入图片描述
根据上面两张图也可以看出** O ( N ! ) O(N!) O(N!)、 O ( 2 N ) O(2^N) O(2N)、 O ( N 2 ) O(N^2) O(N2)**等这几个复杂度都不是很好，时间N对于算法效率的影响过大，所以在后续代码的开发应该减少这些复杂度的算法的使用。
2.2 算法实战
以上详细介绍了复杂度的相关内容，下面回到一开始的旋转数字的算法题，根据题目对于复杂度的要求完善代码。
2.2.1 思路一
时间复杂度： O ( N 2 ) O(N^2) O(N2)
空间复杂度： O ( 1 ) O(1) O(1)
方法：循环K次将数组所有数组都向后移动一位（代码不通过）
void rotate(int* nums, int unmsSize, int k)
{
while(k--)
{
int end = nums[numsSize - 1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i - 1] = nums[i];
}
nums[0] = end;
}
}
补充：利用for循环解决数组前后移动问题
- 可以先将括号内的循环体写出，可以将自己的书写习惯定下来，在这里规定等号右边都用 i 来表示下标
- 如果是左（后）移，等号左边的数组下标就为 i - 1
- 如果是右（前）移，等号左边的数组下标就位 i + 1
- 其中关于for语句中的参数设置，可以画图或者写特殊情况寻找规律，写出参数。
2.2.2 思路二
时间复杂度： O ( N ) O(N) O(N)
空间复杂度： O ( N ) O(N) O(N)
方法：申请新数组空间，先将后K个数据放到新数组中，再将剩下的数据挪到新数组中
int rotate(int* nums; int numsSize; int k)
{
int newArr[numsSize];
for(int i = 0; i < numsSize; i++)
{
newArr[(i + k) % numsSize] = nums[i];//将后K个数组放到新数组前面，在把剩下的挪到新数组
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];//因为最后需要打印数组nums，所以需要赋值回去
}
}
补充1：利用取模符号（%）合理控制一段数字的变化
上述代码第6行是这个算法的关键，一个语句就实现了将后K个数组放到新数组前面，在把剩下的挪到新数组的目的。具体逻辑如下（假设k = 3， numsSize = 7）：
- 当i = 0时，(i + k) % numsSize = 3 则第6行表示，将原数组的第一个数据移到新数组的第四个位置。
- 当i = 1时，(i + k) % numsSize = 4 则第6行表示，将原数组的第二个数据移到新数组的第五个位置。
- ·······
- 当i = 4时，(i + k) % numsSize = 0 则第6行表示，将原数组的第五个数据移到新数组的第一个位置。
- 当i = 5时，(i + k) % numsSize = 1 则第6行表示，将原数组的第六个数据移到新数组的第二个位置。
- 当i = 6时，(i + k) % numsSize = 2 则第6行表示，将原数组的第七个数据移到新数组的第三个位置。
通过取模配合（i + k）可以控制下标在k之前（0~3）的数据放到新数组的下标为（i + k）的位置上去，并且将下标在k之后（4~6）的数据放到下标为（i + k）% 7的位置上去。
补充2：算法效率的优化
以上代码输入到答题框提交上去之后，发现可以通过。这就实现了算法的优化，对比前一个未能通过的代码思考2中的代码，通过用空间复杂度的提升换取时间复杂度的降低，又因为空间复杂度的影响因素一般不大，从而实现算法的优化。
2.2.3 思路三
时间复杂度： O ( N ) O(N) O(N)
空间复杂度： O ( 1 ) O(1) O(1)
方法：
- 前n - k个逆置：4 3 2 1 5 6 7
- 后k个逆置：4 3 2 1 7 6 5
- 整体逆置：5 6 7 1 2 3 4
/*
函数功能：实现一段数据的逆置
参数：
nums：数组名
begin：逆置数据的起始下标
end：逆置数据的结束下标
返回值：无
*/
void reverse(int* nums,int begin,int end)
{
while(begin<end)
{
int tmp = nums[begin];
nums[begin] = nums[end];
nums[end] = tmp;
begin++;
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
//防止逆置时发生数组越界
k = k%numsSize;
//前n-k个数据逆置
reverse(nums,0,numsSize-k-1);
//后k个数据逆置
reverse(nums,numsSize-k,numsSize-1);
//整体逆置
reverse(nums,0,numsSize-1);
}
3. 补充练习
3.1 练习1
分析一下函数的空间复杂度
int** fun (int n) { int** s = (int**)malloc(n * sizeof(int*)); while(n--) { s[n] = (int*)malloc(n * sizeof(int)); } return s; }
分析：
此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3，…n列，所以一共有n(n + 1)/2个元素，故空间复杂度由大O渐进表示法可得为 O ( N 2 ) O(N^2) O(N2)。
代码分析：
int** s = (int**)malloc(n * sizeof(int*));
这行代码是的目的是为列指针分配内存，这行代码为二维数组的列指针数组 s 分配了内存。s 是一个指向 int* 的指针（即指向行的指针）。它可以容纳 n 个 int* 类型的指针，每个指针都将指向一行的内存。
while(n--)
{
s[n] = (int*)malloc(n * sizeof(int));
}
这行代码的目的是为每一行分配内存，这个 while 循环遍历 n，每次为 s[n] 分配 n 个 int 类型的内存空间。每一行都是 n 个 int 类型的数组（注意这里的n会逐行递减）
