【数据结构】时间复杂度和空间复杂度的计算
目录
一、数据结构
1、什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。简单来说，数据结构就是对数据进行管理（增删查改）的一系列操作。
数据结构和数据库的作用很相似，二者的区别在于管理的位置不同：当数据量很大时，数据一般都会存放在磁盘中，此时我们用数据库进行管理；当数据量相对较小时，我们用数据结构来管理。
2、什么是算法
算法 (Algorithm) 就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
数据结构和算法是相辅相成的，二者是我中有你、你中有我的关系：在一个数据结构中可能会用到算法来优化，一个算法中也可能用到数据结构来组织数据。
3、数据结构和算法的重要性
在校园招聘的笔试：
目前校园招聘笔试一般采用Online Judge (在线OJ) 形式， 一般都是20-30道选择题+2道编程题，或者3-4道 编程题。
可以看出，现在公司对我们代码能力的要求是越来越高了，大厂笔试中几乎全是算法题而且难度大，中小厂的笔试中才会有选择题。算法不仅笔试中考察，面试中面试官基本都会让现场写代码。而算法能力短期内无法快速提高，至少需要持续半年以上算法训练积累，否则真正校招时 试会很艰难，因此算法要早早准备。
在校园招聘的面试中：
在面试环节，数据结构和算法也是被经常问到的一部分，大家在牛客、LeetCode的面经中也能够发现这一点，比如如下的一些问题：
- 怎么用两个栈实现一个队列？
- 如何判断两个链表是否相交？
- Vector和数组的区别？
- 红黑树的原理、时间复杂度等？
- map和set底层原理？
- 快速排序思想是什么？
- Hashmap的原理？
在未来的工作中：
这里我引用网上的一篇文章：学好算法对一个程序员来说是必须的吗？如果是，至少应该学到哪种程度
4、如何学好数据结构和算法
关于这个问题的答案，我想大家都知道，要想学好数据结构和算法，除了多练还是多练，至少我们需要把《剑指offer》《程序员代码面试指南》全部刷完，LeetCode至少刷几百道题，然后就是注意在做具体题目之前要先画图分析，理清思路之后再下手。
剑指offer 程序员面试经典 LeetCode OJ 题库
二、算法效率
算法的复杂度
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎；但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度；所以我们如今已经不需要再特别关注一个算法的空间复杂度，而更注重于时间复杂度。
算法复杂度在校招中的考察
三、时间复杂度
1、时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。(这里的函数指的是数学中的函数，而不是我们C语言中的函数) 一个算法执行所耗费的时间，从理论上说是不能算出来的，因为只有当我们把程序放在机器上跑起来，才能知道具体时间。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。 一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
2、时间复杂度的表示方法
我们计算时间复杂度时不是计算算法运行的具体次数，而是用大O的渐进表示法来计算，其具体计算方法如下：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。
3、算法复杂度的三种情况
算法的复杂度分为三种情况：
- 最坏情况：任意输入规模的最大运行次数(上界)
- 平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x 最好情况：1次找到 平均情况：N/2次找到 最坏情况：N次找到 平均情况：N/2次找到 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。
4、简单时间复杂度的计算
例1：
void Func(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}上面程序具体执行的次数：100 用大O的渐进表示法得出时间复杂度：O(1) (用常数1取代运行时间中的所有加法常数。)
例2：
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);
}上面程序具体执行的次数：N * N + 2*N + 10 用大O的渐进表示法得出时间复杂度：O(N^2) (只保留最高阶项)
例3：
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);
}上面程序具体执行的次数：2*N + 10 用大O的渐进表示法得出时间复杂度：O(N) (如果最高阶项存在且不是1，则去除与这个项目相乘的常数
5、复杂时间复杂度的计算
（1）冒泡排序的时间复杂度
void BubbleSort(int arr[], int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}具体执行次数：时间复杂度计算时以最坏情况为准，则假设数组开始是逆序的，那么第一次排序执行 n-1 次，第二次排序执行 n-2 次，第三次执行 n-3 次 … …，直到最后达成有序，所以冒泡排序的具体执行次数是一个等差数列，具体次数 = (首项+尾项)/2*项数 = (N^2-N)/2 用大O的渐进表示法得出时间复杂度：O(N^2)
（2）二分查找的时间复杂度
int BinarySearch(int arr[], int n, int x) //n元素个数 x:要查找的数
{
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = (left + right) / 2;
if (arr[mid] > x)
{
right = mid - 1; //中间元素比x大就挪动right下标
}
else if (arr[mid] < x)
{
left = mid + 1; //中间元素比x小就挪动left下标
}
else
return mid; //找到就返回该元素所在的下标
}
return 0; //找不到就返回0
}具体执行次数：和上面一样，这里考虑最坏情况，即数组中没有想找的元素，数组会从中间开始查找，每次排除掉一半的元素，直到把所有元素排除完，第一次排除后剩下 1/2 的元素，第二次排除后剩下 1/4 元素，第三次排除后剩下 1/8 元素 … …，设元素个数为N，查找次数为X，则 X * (½)^N = 1 -> (½)^N = X -> 具体次数：X = log2N 用大O的渐进表示法得出时间复杂度：O(logN) 注：因为在键盘上无法表示出log的底数，所有在时间复杂度中把log的底数2省略掉了，直接用logN表示log2N的时间复杂度。
（3）阶乘递归的时间复杂度
long long Factorial(int N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}具体次数：这里 n 调用 n-1 , n-1 调用 n-2 …，直到 n = 1，所以一共执行了 n-1 次。 用大O的渐进表示法得出时间复杂度：O(N)
以五的阶乘示例：
（4）斐波那契递归的时间复杂度
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
具体次数：以上图为例，我们可以看到在数值大于2的时候，每一层的调用次数是以2的指数形式增长的，是一个等比数列。 用大O的渐进表示法得出时间复杂度为：O(2^N)
五、不同时间复杂度效率的比较
我们可以看到当测试数据很大时 O(logN) 和 O(1) 的效率几乎是一样的，所以二分查找是一种效率很高的算法，但是它也有一个缺陷，那就是它操作的数组元素必须是有序的。
四、空间复杂度
1、空间复杂度的概念
空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似，也使用大O的渐进表示法。 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
2、空间复杂度的计算方法
空间复杂度的计算方法和时间复杂度非常相似，且都是用大O的渐进表示法表示。 具体计算方法如下：
- 用常数1取代运行过程中定义的常数个变量。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。
3、常见空间复杂度的计算
（1）冒泡排序的空间复杂度
void BubbleSort(int arr[], int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}这里我们在循环外部定义了两个变量，然后在循环内部又定义了一个变量；可能有的同学会认为temp变量因为在循环内部，每次进入循环都会被重新定义，所以空间复杂度为N^2，其实不是的； 我们知道虽然时间是累积的，一去不复返，但是空间是不累积的，我们可以重复使用；对于我们的temp变量来说，每次进入if这个局部范围时开辟空间，离开这个局部范围时空间销毁，下一次在进入时又重新开辟空间，出去又再次销毁；所以其实从始至终temp都只占用了一个空间； 所以上面一共一共定义了三个变量，用大O的渐进表示法得到空间复杂度为O(1)。
（2）二分查找的空间复杂度
int BinarySearch(int arr[], int n, int x) //n元素个数 x:要查找的数
{
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = (left + right) / 2;
if (arr[mid] > x)
{
right = mid - 1; //中间元素比x大就挪动right下标
}
else if (arr[mid] < x)
{
left = mid + 1; //中间元素比x小就挪动left下标
}
else
return mid; //找到就返回该元素所在的下标
}
return 0; //找不到就返回0
}和冒泡排序的空间复杂度一样，这里只定义了三个（常数个）变量，所以空间复杂度是O(1)。
（3）阶乘递归的空间复杂度
long long Fac(int N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}我们知道，每次函数调用开始时都会在栈区上形成自己的函数栈帧，调用结束时函数栈帧销毁； 对于上面的递归来说：只有当 N < 2 的时候函数才开始返回，而在这之前所形成的 Fac(N) Fac(N-1) Fac(N-2) … 这些函数的函数栈帧在返回之前都不会释放，而是一直存在，知道函数一步一步开始返回的时候开辟的空间才会被逐渐释放。所以在计算递归类空间复杂度度时，我们在意的是递归的深度； 这里调用的递归深度为 n - 1（递归 n - 1 次），所以空间复杂度为O(N)。
（4）斐波那契递归的空间复杂度
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
首先就，斐波那契是逐个分支进行递归的，以上图为例，它会先递归6-5-4-3-2-1，再递归6-5-4-3-2，再递归6-5-4-2，以此类推，直到把最后一个分支递归完； 其次，空间是不会累积的，所以尽管我们同一个函数的函数栈帧会被开辟很多次，但是它仍然只计入一次开辟的空间复杂度。 所以递归调用开递归的深度，这里的空间复杂度为O(N)。
五、总结
- 时间复杂度和空间复杂度都是用大O的渐进表示法来表示。
- 时间复杂度看运算执行的次数，空间复杂度看变量定义的个数。
- 在递归中，时间复杂度看调用的次数，空间复杂度看调用的深度。
- 时间是累积的，一去不复返；空间是不累积的，可以重复利用。
- 冒泡排序的时间复杂度为O(N^2)，空间复杂度为O(1)。
- 二分查找的时间复杂度为O(logN)，空间复杂度为O(1)。
- 阶乘递归的时间复杂度为O(N)，空间复杂度为O(N)。
- 斐波那契递归的时间复杂度为O(2^N)，空间复杂度为O(N)。
腾讯云开发者
