一个错误,快排空间复杂度是O(logn),其实logn大多数和树、二分有关。因为上面提及了不断把原问题分解成两个子问题,比如16每次除以2,什么时候到1呢?4次,因为2^4=16,进而4=log(16),其实这个4是二叉树的树高,也就是递归的深度,每下一层就是新的一次递归,也就是空间复杂度,因为快排的递归树高范围[logn,n],n是单支树,可以说是二叉树退化成链表,或者数组已经有序等等,所以平均是O(logn),这些内容在算法导论上都有,有闲下时间可以了解下
点赞

相关推荐

05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务