空间复杂度计算超全整理!!(一起手撕复杂度计算 |
您所在的位置:网站首页 › 数据类型存储空间大小怎么算 › 空间复杂度计算超全整理!!(一起手撕复杂度计算 |
承接上文:算法效率与时间复杂度(8条消息) 时间复杂度计算超全整理!!(数据结构和算法的第一步_vpurple__的博客-CSDN博客 目录 0.前言 1.空间复杂度 1.1 大O的渐进表示法 1.2举几个计算空间复杂度的例子 1.2.1 计算冒泡排序的空间复杂度 1.2.1计算阶乘递归的时间复杂度 1.2.3计算用数组实现还有用变量实现的斐波拉契数列的空间复杂度 1.2.4计算用递归实现的斐波拉契数的空间复杂度 2.常见复杂度的对比 0.前言相比而言现在算法不那么关注空间复杂度,因为现在的设备的存储空间都比较大。 1GB=1024*1024*1024字节 1GB 大概是10亿字节 1MB 大概是100万字节 1GB=1024MB 1MB=1024KB 1KB=1024字节 1.空间复杂度空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 ,也就是额外占取的空间的大小。 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。 注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 1.1 大O的渐进表示法大O符号(Big O notation):是用于描述函数渐进行为的数学符号。 O()括号里面的数更多的表达的是这个算法的量级,大O是一个估算,并不是准确的执行次数。 推导大O阶方法: 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中,只保留最高阶项。 3、如果最高阶项系数存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。 1.2举几个计算空间复杂度的例子 1.2.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; } }冒泡排序的空间复杂度为:O(1) 分析如下: 阶乘递归的时间复杂度:O(N). 分析如下: |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |