ai制作网页,槐荫区网络营销seo,wordpress接入微博,网站建设策划结束语之前发布了数据结构#xff08;一#xff09;#xff0c;很多同学反响不够清晰#xff0c;那今天就发一篇对复杂度专题的博客#xff0c;希望对大家理解复杂度提供一些帮助。
时间复杂度
我们先来一个理解一个复杂度#xff0c;二分查找的复杂度#xff08;之前写过二…之前发布了数据结构一很多同学反响不够清晰那今天就发一篇对复杂度专题的博客希望对大家理解复杂度提供一些帮助。
时间复杂度
我们先来一个理解一个复杂度二分查找的复杂度之前写过二分查找的专题博客感兴趣的可以看一看 CSDNhttps://mp.csdn.net/mp_blog/creation/editor/135742310
我们在数据结构一中讲解了但是没有画图现在为了方便大家的理解现在我重新讲解一下。
我们先把代码拿出来看看
// 计算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 mid1;
else if (a[mid] x)
end mid-1;
else
return mid;
}
return -1;
}
这时候大家会好奇该如何计算其复杂度其实搞清楚原理也比较容易理解。
二分查找的原理就不在过多的讲解了不懂的小伙伴可以去看看上面的链接。
我们还是老样子画图来为大家演示 当我们在不断地缩减直到缩减到只剩下一个值的时候。 那么这就是最坏的一个情况如果这个值是我们想要找的那个值那么就找到了如果不是那么我们输出找不到。
随之而来的疑问就是我们一共找了多少次呢
假设我们有N个值我们每次都缩减一半那么就是N/2,这是一次。那么我们一共找了多少次呢
N/2/2/2/2/2/2.............1 直到我们找到那个数为止。 这是最坏情况那么我们除了多少个2呢
不难看出其实我们找了多少次就除了多少个2。
关键点拨假设我找了X次那么我们 就可以得到表达式。
第一步N/2/2/2/2/2/2/2...............1
第二步N1*2^x 等式两边同时乘2
第三步2^xN
第四步化简 基本操作执行最好1次最坏O(logN)次时间复杂度为 O(logN) pslogN在算法分析中表示是底 数为2对数为N。有些地方会写成logN 。由于对数在键盘中不好敲出来所以我们通常省略2。 补充时间复杂度例题
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}
大家看到这串代码时一定有想骂街的冲动但是有我在大家不用担心我来为大家搞定它。 那么开始进入正题
上面的代码是 N 的阶乘的原码之前我的博客也写过感兴趣的小伙伴可以去看看地址就放在这里了-用C语言实现阶乘的相加-CSDN博客文章浏览阅读373次点赞11次收藏9次。i3 ret1*2*3 此时的ret6 可以理解为1*2*3。i2 ret1*2 此时ret2 可以理解为1*2。当n2时ret1*2 同样把值存在sum中 此时的ret2。ret开始变化 例如当for循环运行到i3时i1 ret1*1 此时ret1。那么我们有没有其他方案呢答案是有的我们可以这样在求2的阶乘时直接在1的阶乘上乘2 1*2。关键点拨retret*n 当n1时ret1*1 并把值存在sum中。https://blog.csdn.net/weixin_73496371/article/details/135739915。
这里我们就直接开始我们先思考一个问题阶乘调用了多少次函数
老样子画图解释 我们不断调用FAC从N次到N-1次再到N-2次...........直到0次
我们把它们相加起来就可以得到。
计算分析发现基本操作递归了N次时间复杂度为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^3..........它们实际上是一个等比数列。
我们使用等比数列求和的方式求和. 这就用到了我们的高中知识。 通过计算分析发现基本操作递归了2^N次时间复杂度为O(2^N)。
接下来为大家详解空间复杂度 空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 实例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;
}
}
结论 实例1使用了常数个额外空间所以空间复杂度为 O(1)
解释空间复杂度是我们一个算法在运行时额外由于逻辑的需要开辟的空间。
上述代码算法排序过程额外开辟的有 size_t end size_t i exchange它们开辟的空间都是常数所以使用大O渐进法不难算出空间复杂度。 O(1) 如果大家对这道题有疑问的话我们再来看一道题相信你的问题不在是问题了。 实例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
if(n0)
return NULL;
long long * fibArray (long long *)malloc((n1) * 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;
}
我们观察在算法的运行中只动态开辟了n1的空间。 ---------malloc((n1)
那么我们使用大O渐进表示法
动态开辟了N个空间空间复杂度为 O(N)。
到这里我想大家对空间复杂度有了全新的理解了吧。 常见复杂度对比
一般算法常见的复杂度如下 复杂度的oj练习
消失的数字OJ链接. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/missing-number-lcci 感谢你的观看
后续更新更多数据结构的相关知识
