什么是空间复杂度?

菜园前端
• 阅读 186

原文链接:https://note.noxussj.top/?source=helloworld


什么是空间复杂度?

算法在运行过程中临时占用存储空间大小的度量,和时间复杂度表示一样,一个函数,用大 O 表示,例如 O (1)、O (n)、O (^2 )...

基础案例

O(1)

这段代码因为只声明了单个变量,单个变量所占用的内存永远是 1。

let i = 0

i += 1

O(n)

这段代码主要声明了变量 list 和变量 i,但是变量 list 的元素个数会受 n 的影响,所以时间复杂度是 O (n) 而变量 i 的时间复杂度 O (1) 两个相加时可忽略不计。

const list = []

for (let i = 0; i < n; i++) {
    list.push(i)
}

O(n ^ 2)

我们平时用的栅格布局(一行里面包括多少列)其实也可以用矩阵来表示。这段代码主要声明了 matrix 变量,是一个数组,因为是嵌套循环,所以数组的元素个数为 n * n 为 n ^ 2。

const matrix = []

for (let i = 0; i < n; i++) {
    matrix.push([])

    for (let j = 0; j < n; j++) {
        matrix[i].push(j)
    }
}
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
java常用类(2)
三、时间处理相关类Date类:计算机世界把1970年1月1号定为基准时间,每个度量单位是毫秒(1秒的千分之一),用long类型的变量表示时间。Date分配Date对象并初始化对象,以表示自从标准基准时间(称为“历元”(epoch),即1970年1月1日08:00:00GMT)以来的指定毫秒数。示例:packagecn.tanjian
Easter79 Easter79
2年前
sql注入
反引号是个比较特别的字符,下面记录下怎么利用0x00SQL注入反引号可利用在分隔符及注释作用,不过使用范围只于表名、数据库名、字段名、起别名这些场景,下面具体说下1)表名payload:select\from\users\whereuser\_id1limit0,1;!(https://o
Stella981 Stella981
2年前
Redis 列表命令记录
新增的常用命令从列表右端插入值(1N个)(rpushlistkeycba)rpushkeyvalue1value2...valueN时间复杂度为O(1N)从列表左端插入值(1N个)(lpushlistkeycba)lpushkeyvalue1
Stella981 Stella981
2年前
Lua ip to int 和 int to ip
function_M.ipToInt(str)localnum0ifstrandtype(str)"string"thenlocalo1,o2,o3,o4str:match("(%d)%.(%d)%.(%d)%.(%d)")num2^24o1
Wesley13 Wesley13
2年前
O2O 行业 IT 系统架构实践分享——预告
主题:O2O行业IT系统架构实践分享时间:4月26日20:00——21:30地点:QingCloud技术分享群报名方式:扫描文末小编二维码添加好友,发送听课,小编拉你进群。讲师:张卫华,青云QingCloud架构和解决方案工程师。本期内容介绍:O2O作为一种新生的商业模式,经过这些年的实践和讨论,已
Wesley13 Wesley13
2年前
ES6(六)数值的扩展
二进制和八进制表示法ES6提供了二进制和八进制数值的新的写法,分别用前缀0b(或0B)(二进制binary)和0o(或0O)(八进制octonary)表示。0b111110111503//true0o767503//true从ES5开始,在严格模式之中,八进制就不再允许使用前缀0表示,E
Wesley13 Wesley13
2年前
BFPRT线性查找算法
介绍:BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。时间复杂度O(N)算法步骤
菜园前端 菜园前端
10个月前
什么是时间复杂度?
原文链接:什么是时间复杂度?定性描述该算法的运行时间,一个函数、用大O表示,例如O(1)、O(n)、O(logN)...常见的时间复杂度量级常数阶O(1)对数阶O(logN)线性阶O(n)线性对数阶O(nlogN)平方阶O(n²)立方阶O(n)K次方阶O(
菜园前端 菜园前端
9个月前
什么是顺序搜索?
原文链接:什么是顺序搜索?顺序搜索是一种比较低效的搜索算法,但是实现起来相对简单。主要步骤如下:1.遍历数组2.找到跟目标值相等的元素,就返回它的下标3.遍历结束后,如果没有搜索到目标值,则返回1基础案例时间复杂度:O(n)空间复杂度:O(1)javasc
京东云开发者 京东云开发者
3个月前
时间复杂度为 O (n^2) 的排序算法 | 京东物流技术团队
对于小规模数据,我们可以选用时间复杂度为O(n2)的排序算法。因为时间复杂度并不代表实际代码的执行时间,它省去了低阶、系数和常数,仅代表的增长趋势,所以在小规模数据情况下,O(n2)的排序算法可能会比O(nlogn)的排序算法执行效率高。不过随着数据规模增