深度剖析基础数据结构系列第一章——开胃小菜之复杂度
目录
【前言】：前天有位铁汁建议我更新数据结构这块内容，原本我是打算放到两个月之后的，不过呢那位老铁是真的迫切，但是我精力有限，所以昨天晚上我认真想了一下，决定把零基础搞定C语言系列压缩一下，也就是说，C语言就不每个知识点都讲一遍了，毕竟CSDN中有很多关于C语言优秀的文章，所以我直接把我认为重要的，以及一些易错点写出来，再夹带着一些笔试题，这样的话时间稍微充裕些。
【声明】：数据结构已经拉开序幕咯，可能有点晚，但是笔者会尽量跟上的哦，铁汁们上车了没！？
嘿嘿，铁汁们的要求我会尽量满足的，不负代码不负卿哦！
一、什么是时间复杂度和空间复杂度？
1.算法效率
算法效率分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度， 而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主 要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间 复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。 所以我们如今已经不需要再特别关注一个算法的空间复杂度。
前面巴拉巴拉赘述了这么多，我们只需要知道，算法效率分为两种：一是时间效率，二是空间效率；时间效率被称为时间复杂度， 而空间效率被称作空间复杂度。
2.时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运 行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机 器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻 烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比 例，算法中的基本操作的执行次数，为算法的时间复杂度。
【敲黑板】：算法中基本操作的执行次数，为算法的时间复杂度。
3.空间复杂度的概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用 了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数
【敲黑板】：空间复杂度算的是变量的个数
注意注意，一定要注意：时间复杂度算的不是时间，算的是基本操作的执行次数；空间复杂度算的不是空间，算的是变量的个数。
4.复杂度计算在算法的意义
其实很多公司在招聘的时候，数据结构和算法这块是考察的重点，在算法笔试题里面几乎都会考察应聘者对复杂度的计算和理解。所以，铁汁们，这块内容虽然不难，但却是重点哦，不能掉以轻心！上面难理解或者是容易想错的地方都已经明确标记出来咯，抓紧时间记住哈。加油加油！！
二、如何计算常见算法的时间复杂度？
【敲黑板】：实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法
1、用常数1取代运行时间中的所有常数。
2、在修改后的运行次数函数中，只保留最高阶项，去除那些对结果影响不大的项
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。
得到的结果就是大O阶，所以大O的渐进表示法只是一个估算。
可能你不是很理解上面推导大O阶方法，没关系，下面给出几道例题，你很快就能理解啦！
-
//计算Func1基本操作执行了多少次
-
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++;
-
}
-
}
Func1()基本操作的执行次数：
F(N) = N ^ 2 + 2 * N + 10 ;
随着N的增大，N ^ 2对结果的影响是最大的
而时间复杂度只是一个估算，所以仅仅取决于表达式中对结果影响最大的那一项
所以，本题的时间复杂度为 O(N ^ 2)
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)；
平均情况：任意输入规模的期望运行次数；
最好情况：任意输入规模的最小运行次数(下界)。
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N）
复杂度对比
O(1)是最好的，其次是O(logN)...
常见的时间复杂度：
O(N) O(N ^ 2) O(log N) O(1)
而空间复杂度就不像时间复杂度这么复杂了，一般情况下空间复杂度都是O(1)，因为时间是累计的，而空间却不是累计的。比如循环走了n次，其实利用的是一个空间，因为变量往回走的时候，就会销毁原先开辟的空间，现在暂时不理解也没有关系，后面有大量的练习呢。
三、典型复杂度要求的算法题练习
实例1
-
void Func2(int n)
-
{
-
int count = 0;
-
for (int k = 0; k < 2 * n; k++)
-
{
-
count++;
-
}
-
int m = 10;
-
while (m--)
-
{
-
count++;
-
}
-
}
Func2()基本操作的执行次数：
F(N) = 2 * N + 10
随着N的增大，2 * N 对结果的影响是最大的，又因为其系数不是1，所以要去除与N相乘的常数2
所以，本题的时间复杂度为：O(N)
实例2
-
int Func(int n, int m)
-
{
-
int count = 0;
-
for (int k = 0; k < m; k++)
-
{
-
count++;
-
}
-
for (int i = 0; i < n; i++)
-
{
-
count++;
-
}
-
}
Func3()基本操作的执行次数：
F(N) = m + n
如果说明m 远大于 n, 则时间复杂度为O(M)；
如果说明m 约等于 n, 则时间复杂度为O(N)；
如果没有说明，则时间复杂度为O(M + N)
实例3
-
void Func4(int n)
-
{
-
int count = 0;
-
for (int k = 0; k < 100; k++)
-
{
-
count++;
-
}
-
}
可能你以为是O(100)，但是不是哦，是O(1)
实例4
-
const char* strchr(const char* str, char character)
-
{
-
while (*str != '\0')
-
{
-
if (*str != character)
-
{
-
return str;
-
}
-
str++;
-
}
-
return NULL;
-
}
假设字符串的长度为N，则本题时间复杂度为O(N)
实例5：二分查找
前提：数组是有序的！！
-
int Binary_search(int* arr, int n, int k)
-
{
-
int left = 0;
-
int right = n - 1;
-
int mid = 0;
-
while (left <= right)
-
{
-
mid = (left + right) / 2;
-
if (arr[mid] > k)
-
{
-
right = mid - 1;
-
}
-
else if (arr[mid] < k)
-
{
-
left = mid + 1;
-
}
-
else
-
{
-
return mid;
-
}
-
}
-
return -1;
-
}
想象一张电费条：长度为n (n / 2^0)
第一次砍一半剩：n / 2 (n / 2^1)
第二次砍一半剩：n / 4 (n / 2^2)
第三次砍一半剩：n / 8 (n / 2^3)
...
假设砍了x次找到了：n / 2^x = 1
所以有，2^x = n ---> x = log n
所以二分查找的时间复杂度为：O(logN)
实例6：单路递归
-
int func(int n)
-
{
-
if (n == 1)
-
{
-
return 1;
-
}
-
return n + func(n - 1);
-
}
递归调用了n次，每一次递归运算的时间复杂度为O(1)，所以n次就是O(N)；
但是要注意的是，本题的空间复杂度不再是O(1)。
这里就需要补充一下递归函数调用的知识点了，每次调用递归函数都需要建立一个栈帧，而每个栈帧又都使用了常数个空间，递归函数的空间复杂度取决于递归调用栈的深度，所以很明显，本题空间复杂度为O(N)
【敲黑板】：递归函数调用时建立栈帧，返回时销毁。
实例7：多路递归
斐波那契数列递归：
题目描述：求斐波那契数列的第N项，1 1 2 3 5 8 13 21...
-
int fib(int n)
-
{
-
if (n == 1 || n == 2)
-
{
-
return 1;
-
}
-
return fib(n - 1) + fib(n - 2);
-
}
本题非常典型，属于多路递归，可以将它画成二叉树的形式：
但是求时间复杂度的时候，我们要的是最坏的情况，所以假设成满二叉树，时间复杂度就是该二叉树节点的个数，也就是O(2^N);
空间复杂度为这棵树的高度，所以是O(N)
结语
数据结构第一章的内容到此结束咯，欢迎铁汁们留言评论哈，你们的支持就是我最大的动力，当然啦，觉得有所收获的铁汁，麻烦动动小手，给俺个三联吧，求求啦！
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/121092896
- 点赞
- 收藏
- 关注作者
评论（0）