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

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

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


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


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




  

相关话题

  0x5f3759df这个快速开方中的常数的数学依据是什么? 
  公司规定所有接口都用 post 请求,这是为什么? 
  只会nodejs,但公司强制要求上php,是让他们招个phper,还是自己去学? 
  如何评价微信小程序内嵌网页功能开放? 
  《阮一峰版快速排序完全是错的》一文是否存在事实错误? 
  作为一个前端小白,应该从那些方面开始学习? 
  为什么某些人说 JavaScript 是不成熟的语言? 
  为什么form表单提交没有跨域问题,但ajax提交有跨域问题? 
  算法源于大数据,而大数据源于我们每一个人,那我们是不是应该拥有主导数据的权利? 
  为什么加载 JavaScript 使用 src,加载 CSS 使用 href? 

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





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