如何实现空间复杂度O(1)的快排

在这个《算法分析与设计》Michael.T.Goodrich 一书中看到这个说法，有可能实现这种非递归的O(1)的空间复杂度的快排吗

anyex 2022-10-12 第1期

源自：排序 1-7 快速排序

20

收起

1回答

山行老师 2022-10-13 00:42:52

不可能，快排怎么都跟问题规模相关，时间复杂度不可能为常数项

提问者 anyex #1

空间复杂度O(1)呢，因为递归方式如果对大量数据排序可能有栈溢出的风险，看这个里面的介绍感觉是有实现常数级空间复杂度的快排的方案

2022-10-13 09:43:37
山行老师 #2

有空间复杂度不变的，那就是确定好用几个指针来排序(不一定是快排)，比如冒泡排序，不管排序元素是100个还是1000，需要的指针变量不会随着问题规模变大，这样的算法空间复杂度就是O(1)

2022-10-31 13:28:00

相似问题

递归的时间和空间复杂度

可以这样来看双路快速排序的算法复杂度吗

关于复杂度计算的问题

Leetcode 809 时间复杂度

Leetcode 875吃香蕉的时间复杂度

登录后可查看更多问答，登录/注册

物联网/嵌入式工程师

参与学习 394 人
提交作业 22954 份
解答问题 1163 个

行业热门，政策风口，人才缺口极大，现在入场时机正好！上千人检验，数轮迭代的硬核知识体系，软硬件通吃保姆式教学+简历指导+1V1模拟面试+3次内推，助力轻松就业！

本课精华内容

问答作业

实在是不知道怎么写回调函数的形参，报错是看懂了，解决方案想不出来

37 13

关于接收到的第三和第四数据

19 10

if(ch=='\33')是判断啥的呢？

53 9

这里的命令置换怎么理解

18 9

关于物理内存分配疑问

26 9

查看更多本课问答

请稍等 ...

意见反馈帮助中心 APP下载