百科问答小站 logo
百科问答小站 font logo



《阮一峰版快速排序完全是错的》一文是否存在事实错误? 第1页

  

user avatar   winter-25 网友的相关建议: 
      

讲技术的部分:

  1. 之前我一直误认为自己写的原地快排的空间复杂度是O(1),但是通过这次网友的提醒(该网友已在评论区出现 @原建业 ),我发现居然是O(log(n)),因为递归不是尾递归必须用栈,思考了下,好像并没有办法优化,怎么写都要O(log(n))。
  2. 非原地快排,就算敞开了铺着写,假设我们每层递归都产生临时数组,那么空间占用应该是 n + n/2 + n/4 + n/8 + …… ≈ 2n,也就是说,空间复杂度是O(n)
  3. 众所周知,快排进行了log(n)次O(n)的partition,所以时间复杂度是O(nlog(n)),阮老师犯下了“弥天大罪”在每次partition之前选取中间值的时候进行了一次splice,而splice的时间复杂度是O(n),partition的时间复杂度也是O(n),请问O(n) + O(n)是?

结论:阮老师写的是非原地快排,空间复杂度从O(log(n))上升到了O(n),而每次使用splice从无序的数组中间位置选取中值是毫无意义的浪费,但并没有改变时间复杂度,他写的快排时间复杂度仍然是O(nlog(n))。从实际测试结果来看,阮老师的代码性能也确实不高。

PS.阮老师这篇作于2011年,那时候阮老师的职业是什么,大家不妨了解下。


讲人的部分:

这位ideawu其人,张口闭口前端如何,透露出一股优越感,令人生厌:

“大多数前端只会表面皮毛”

"前端的天花板实在太低了"


这位同学非常有意思,你跟他讲时间复杂度,他跟你讲性能,你跟他讲性能,他跟你讲次数???在我提供了性能优于他的代码之后,他这样说:


最后,我想说,题主倒是个明白人,跟着瞎起哄的,你们可长点心吧……




  

相关话题

  N 个乒乓球中有一个和其他的质量不同,用天平最少几次一定能称出来? 
  各个编程语言都有哪些「亮点」? 
  数据结构与算法在工作的作用及其大学学到什么程度才算可以? 
  如何通俗易懂地解释遗传算法?有什么例子? 
  框架用比不用的真正优势? 
  王垠的《谈谈Parser》是在回应 winter 吗? 
  请问各位程序员,是我的思维方式有错误吗? 
  毕设答辩,老师说node不可能写后台怎么办? 
  如何看待 2022 年秋招算法岗竞争如此激烈? 
  为什么大学不教javaScript? 

前一个讨论
如何把一段简单的代码变复杂?
下一个讨论
为什么霍格沃茨没有扫帚航空指挥塔台?





© 2025-05-02 - tinynew.org. All Rights Reserved.
© 2025-05-02 - tinynew.org. 保留所有权利