阜新市建设小学网站重庆博达建设集团网站

当前位置： 首页 > news >正文

阜新市建设小学网站,重庆博达建设集团网站,电子商务网站计划书,上杭网站定制全文目录引言空间复杂度例题test1test2#xff08;冒泡排序#xff09;test3#xff08;求阶乘#xff09;test4#xff08;斐波那契数列#xff09;总结引言 在上一篇文章中#xff0c;我们提到判断一个算法的好坏的标准是时间复杂度与空间复杂度。 时间复杂度的作用… 全文目录引言空间复杂度例题test1test2冒泡排序test3求阶乘test4斐波那契数列总结引言 在上一篇文章中我们提到判断一个算法的好坏的标准是时间复杂度与空间复杂度。 时间复杂度的作用是衡量一个算法运行的快慢而空间复杂度是衡量一个算法运行所需的额外的空间。在上一篇文章中我们已经了解了计算时间复杂度的方法以及如何使用大O阶表示法来表示时间复杂度的大概值。 戳我转到时间复杂度详解哦 在本篇文章中将详细介绍关于空间复杂度的相关内容 空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中所额外占用的空间大小的量度。 在时间复杂度中我们以算法中基本语句执行的次数作为算法的时间复杂度 而空间复杂度中我们以变量被创建的个数作为算法的空间复杂度不论是什么类型的变量都算做一个空间复杂度。 需要注意的是由于函数运行时需要的栈空间在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定参数等一些数据不必计算。 我们在计算空间复杂度时依旧采用大O阶表示法来确定其大概值。 转换大O阶表示的方式与时间复杂度相同 1、用常数1表示算法中的所有加法常数 2、在修改后的数学表达式中只保留最高项 3、如果最高项存在且不是1则去掉该最高项的系数。 但是通常情况下我们是不需要将精确的空间复杂度计算出来后再转换的。与时间复杂度相同空间复杂度的大O阶表示法也分为例如对数级log n、正比例级n、次方级n^2、指数级2^n等 但是对于空间复杂度而言最常见的就是O(1)与O(n)其他量级就不是很常见。 例题 接下来就通过几个栗子来理解空间复杂度 test1 int* rotate(int* nums, int numsSize, int k) {int* ret (int*)calloc(numsSize, sizeof(int));int i 0;for (i numsSize-k; i numsSize ; i){*ret nums[i];}for (i 0; i numsSize - k; i){ret nums[i];}return ret-numsSize; }在这段算法中我们实现了将数组的后k个元素移动到数组的前面。 在计算这个算法的空间复杂度时数组nums、整型numsSize与k均为参数所以不计算空间复杂度。在实现元素的移动时我们动态开辟了一块空间这块动态空间由numsSize个整型所以这个算法的空间复杂度就是O(n)。 不难发现在算法中还创建了一个整型变量i但是这个常数就省略不计了。 test2冒泡排序 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;} }这段算法是经典的冒泡排序。 在段算法中额外申请了三个整型变量end、exchange、i 。空间复杂度是常数大O表示法中常数忽略后表示为O(1)。 test3求阶乘 long long Fac(size_t N) {if (N 0)return 1;return Fac(N - 1) * N; }此算法可以实现求N的阶乘。 在这个算法中我们通过函数递归的方式每次递归将N-1作为参数返回Fac(N - 1) 与 N的乘积。 参数为0时递归终止开始返回值。 这里需要注意的是函数在栈中开辟函数栈帧时是依次开辟的。当函数调用它本身时会在栈中再开辟一块空间作为新的函数的栈帧。在每一块栈帧中并没有创建额外的变量所以我们可以认为每一块栈帧的空间复杂度是常数个。所以有多少次递归就会有多少个函数的栈帧。 我们可以画图来表示在这个算法中栈帧的开辟 从参数为N递归到参数为0共递归了N1次。省略常数1该算法的空间复杂度就是O(n)。 test4斐波那契数列 long long Fib(size_t N) {if (N 3)return 1;return Fib(N - 1) Fib(N - 2); } 此算法通过递归实现计算第n个斐波那契数。 在上一篇文章中我们介绍了这个算法的时间复杂度的计算结果是O(2^n)。通过计算时间复杂度我们了解了这个算法的递归规律 根据上一个例题我们知道在这种没有新建变量的递归中每次递归的空间复杂度都可以看作常数。大概是递归了2^n次那空间复杂度也是O(2^n)吗 其实并不是其实这个算法的空间复杂度是O(n)。 函数调用时会为函数开辟一块栈帧当函数调用结束后这块空间就会被还给操作系统。这块空间是可以重复利用的。比如在调用某函数结束后再次调用相同的函数时所用的空间与上次调用完的空间是相同的这里举一个小栗子 void Fun1() {int i 10;printf(%p\n, i); } void Fun2() {int j 10;printf(%p\n, j); } int main() {Fun1();Fun2();return 0; }这段代码中main函数调用了两个相同的函数Fun1与Fun2。在这两个函数中都创建了一个整型的变量。我们打印这两个变量的地址发现它们是相等的。这就说明这两个函数所使用的是同一块空间。 再回到斐波那契数列。这个算法的递归并不是我们想象的一次递归同时开辟两个函数栈帧而是先在一条线上递归到终止后返回一个值释放此次递归的空间再回到上一级的递归然后再到终止后返回一个值再释放此次的空间然后再回到上一级递归释放空间。最终将所有的返回值汇到最初的函数中得到最终的结果 这张图示应该可以比较清楚地描述该算法的递归 首先顺着第一条线递归直到小于3时终止。到此函数一共递归N-1次空间复杂度为O(n)。返回1后为Fib(2)开辟的栈帧被释放下一步调用Fib(1)并为其开辟空间这时开辟的空间与刚才Fib(2)的空间是同一块该函数的参数也小于3递归终止返回1为Fib(1)开辟的栈帧被释放。此时Fib(N-4)的返回值就可以被计算出来即Fib(2)与Fib(1)的和假设N-4-1的值为2返回后为Fib(N-4)开辟的空间也被释放接下来为Fib(N-5)开辟栈帧该空间与刚才释放的Fib(N-4)的函数栈帧是同一块空间… 依次类推其实该算法开辟的空间就只有最开始第一条线递归时所开辟的空间后面的递归开辟空间时使用的都是之前释放的空间。所以该算法的空间复杂度就是O(n)。 通过这个斐波那契数列的递归算法我们不难发现 时间是一去不复返的在运行基本语句时势必要消耗时间 而空间是可以重复利用的我们在使用完一块空间后该空间被释放后是可以再次利用的。 所以在许多的算法中会使用空间换时间的思想尽量先保证时间复杂度的减少。 总结 在本篇文章中我们了解了空间复杂度的相关知识以及能够计算算法的空间复杂度 到此对于算法效率的判断的两个标准空间复杂度与时间复杂度都已经介绍完了 如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出 如果本文对你有帮助希望一键三连哦 希望与大家共同进步哦