百科问答小站 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其人,张口闭口前端如何,透露出一股优越感,令人生厌:

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

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


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


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




  

相关话题

  C++笔试算法题允许用stl函数吗? 
  如何评价 Ant Design 这个项目(一个设计语言)? 
  为什么有人说弄懂了《算法导论》的 90%,就超越了 90%的程序员? 
  为什么那么多公司做前后端分离项目后端响应的 HTTP 状态一律 200? 
  如何看待某托管在 GitHub 的前端开源项目关闭 Issue 栏目的行为? 
  你在生活中用过最高端的数学知识是什么? 
  Minecraft 的地形生成算法是什么? 
  如何看待前端的响应式编程,后台有类似的实现吗? 
  请问这个式子有没有简便算法(写法)? 
  为什么都说富文本编辑器是天坑? 

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





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