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)，这些内容在算法导论上都有，有闲下时间可以了解下
点赞
相关推荐
投递牛客等公司6个岗位 > 
从零开始的转码生活：很有用，收藏了，不过我想知道如果经历很多但有含金量的很少，是删减成一页还是全部都写上按两页计算呀，是不是简历还是一页更好一点 点赞 评论 收藏
分享
腾讯云智研发一面205人在聊
查看6道真题和解析 牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
223947次浏览 2121人参与
# 硬件人你反向读研了吗 #
41569次浏览 628人参与
# 为了找工作你投递了多少公司？ #
5774次浏览 70人参与
# 小米提前批笔试难吗 #
33114次浏览 352人参与
# 一人一个landing小技巧 #
76924次浏览 1102人参与
# 入职第一天，你准备什么时候下班 #
54512次浏览 348人参与
# 正在实习的你，几点下班 #
156039次浏览 1085人参与
# 担心入职之后被发现很菜怎么办 #
125858次浏览 748人参与
# 一人推荐一个机械人值得去的公司 #
403128次浏览 4136人参与
# 夸夸我的求职搭子 #
192086次浏览 1898人参与
# 校招入职后的感受 #
274499次浏览 2667人参与
# 投格力的你，拿到offer了吗？ #
82418次浏览 573人参与
# 体制内上岸心路历程 #
26527次浏览 212人参与
# 产品每日一题 #
43483次浏览 563人参与
# 实习吐槽大会 #
54750次浏览 281人参与
# 华为池子有多大 #
87450次浏览 689人参与
# 大家每天通勤多久？ #
41726次浏览 326人参与
# 我和mentor的爱恨情仇 #
47662次浏览 299人参与
# 硬件人秋招的第一个offer #
72283次浏览 1112人参与
# 我的租房踩坑经历 #
46186次浏览 409人参与