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

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

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


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


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




  

相关话题

  有哪些新手程序员不知道的小技巧? 
  作为前端开发者,不了解flash,可耻吗? 
  阿里的 UI 设计和 Google Microsoft Apple 的设计是否有差距? 
  为什么java返回json时用code=0表示成功, 而我观察的php和nodejs都是用1表示成功? 
  为什么有些算法工程师从来不谈业务,不谈解决问题,不谈价值挖掘,开口闭口就是算法模型,炼丹调参工程化? 
  已经 2022 年了,学习 JavaScript 继承方式的意义是什么? 
  C#相对路径 连接Access数据库怎么写?? 
  有什么工具可以下载整个网站的内容吗? 
  100个金币,只有1个略重,其余99个一样重。给你一个天平,最少称几次能确保找出那个略重的? 
  如果一瞬间让所有编程语言的0.1 + 0.2 == 0.3,会造成多大影响? 

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





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