ve2102388688
2021-05-14 10:13 电子科技大学 C++
关注
一个错误，快排空间复杂度是O(logn)，其实logn大多数和树、二分有关。因为上面提及了不断把原问题分解成两个子问题，比如16每次除以2，什么时候到1呢？4次，因为2^4=16,进而4=log(16)，其实这个4是二叉树的树高，也就是递归的深度，每下一层就是新的一次递归，也就是空间复杂度，因为快排的递归树高范围[logn,n]，n是单支树，可以说是二叉树退化成链表，或者数组已经有序等等，所以平均是O(logn)，这些内容在算法导论上都有，有闲下时间可以了解下
点赞
相关推荐
查看18道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
230240次浏览 2166人参与
# 职场人，说说你的烦心事 #
8277次浏览 65人参与
# 你认为哪个岗位找工作最卷 #
9501次浏览 34人参与
# 职场上哪些事情令人讨厌 #
16529次浏览 81人参与
# 一人一个landing小技巧 #
78100次浏览 1115人参与
# 秋招最大的收获是什么？ #
33776次浏览 296人参与
# kpi面有什么特征 #
30164次浏览 171人参与
# 大家每天通勤多久？ #
41869次浏览 329人参与
# 小红书求职进展汇总 #
56006次浏览 483人参与
# 职场破防瞬间 #
234794次浏览 2125人参与
# 为了找工作你投递了多少公司？ #
8182次浏览 106人参与
# 职场吐槽大会 #
204815次浏览 1630人参与
# tplink提前批进度交流 #
162559次浏览 1377人参与
# 许愿池 #
283004次浏览 2868人参与
# 机械制造岗投递时间线 #
22655次浏览 345人参与
# 通信硬件牛牛的实习日记 #
7078次浏览 65人参与
# 找工作前vs找工作后的心路变化 #
9540次浏览 102人参与
# 聊聊你的职场新体验 #
157236次浏览 1367人参与
# 经纬恒润求职进展汇总 #
118841次浏览 1027人参与
# 入职第一天，你准备什么时候下班 #
55508次浏览 351人参与