工作五年的游戏后端不知道排序算法的复杂度正常吗？

[Rooger]

最近又要开始招聘了，一直以来，这个问题非常困惑我。有个候选人简历上写着：熟练掌握数据结构和算法。 我问那常见的排序算法有哪些，只说出一个，快速排序。我问那时间复杂度是多少，他说 O(logN)。我无语了。 其实面试了这么多，这个是最让我疼的。毕竟说 O(N)，还不是太离谱。

[ericls]

我面试亚马逊的时候 连 binary tree 是啥都不知道 但是对方给我解释之后 我还是能顺利做出最优解 最后还是拿到了 offer

[guanhui07]

.猜测 O n 方

[mz02005]

估计是面试紧张，把搜索排序结果的复杂度错以为是排序复杂度了

[xsen]

@JohnBull #9 动不动就废物，须不知道你也有成为你口中的废物的一天；当然，对于某些动不动就深以为 Java 中自带的算法，或者 C++中 STL 的算法性能不够，要手撸的人来说——典型的只见树木不见森林，一向都是敬而远之

古人说的文人相轻在不是文人的码农中更为明显，因为他们都要踩着 N 年经验的废物往上爬——但还不只是爬而已

[xsen]

工作中非常不喜欢有某些特征的人：如倾向过度设计、过度优化
在进度都无法满足的情况下，某些人总是纠结于某个节点毫秒级别的优化——娘西皮，摆脱能不能考虑下应用场景、数据量，在明明现在数据量最多也就十万级别，你非要纠结于千万级别的优化

这样的人简单来说，就是不分轻重；对需求与任务连个优先级划分都做不来

[CrazyMonkeyV]

@xsen 二叉树遍历的伪代码又不啥难事，我 10 年后端的老 fw 都没有和他这种 fw 置气，绕他一命

[xsen]

@ericls #101 这确实是国内外企业文化的区别，一个是为了踩人，一个是为了找人

[xsqfjys]

可以不知道，但是不知道就不要写熟练掌握算法

[MEIerer]

应届生都会

[chocotan]

不会正常
但简历写了不正常

[chocotan]

每个人认为的“基础”不一样的
我觉得会写 javadoc 是基础

[sky857412]

国内是真的卷，工作中用不到，忘了就忘了呗。用的时候再查就行了，编程啥时候变成背答案，编程是如何解决一个问题呀。

[xiaojun1994]

我工作五年的前端也不知道，很讨厌算法

[wangyzj]

意思就是面试前没准备呗
万一只是去你那玩玩呢

[unco020511]

正常,但简历这样写却不知道就不正常

[e7]

我不会因为一个问题答不上来就否定一个人，可能没准备可能就是忘了，也有可能就是基础差，但还是可以挖掘下他擅长的地方，用人用所长，如果长处也不行就拒了吧。骐骥，千里马也，驱以捕鼠，不如跛猫。

[shunia]

快速排序（ quick sort ）—O(n*log n)期望时间，O(n^n)最坏情况；对于大的、随机数列表一般相信是最快的已知排序

我看了一下，上面可以认为是回答了的朋友基本都没有把这句话说明白的。
所以 OP 能把这三句短语在面试过程中都表达的清楚明白吗？

非杠，就是感觉有点尴尬。所有人都认为这是几个基础题，但是看起来似乎并没有人真的在这么多讨论里把答案写“全”。

[shunia]

@shunia #117 快速排序（ quick sort ）—O(n*log n)期望时间，O(n^2)最坏情况；对于大的、随机数列表一般相信是最快的已知排序

从 Wiki 复制的，改格式改错了

[Huelse]

让我想起了这个 https://twitter.com/mxcl/status/608682016205344768

[Huelse]

其实我觉得算法问题主要是刷人，智商高的人可能记得很清楚甚至当场推出来，但工作不只需要智商。。。

[lakehylia]

不会很正常，换我也要拿课本复习一下

[2NUT]

不死记硬背

排序算法并不是一个简单的事情。

[debuggerx]

我不会，只知道大致的概念，也懒得仔细学，当然也不会往简历里写，个人认为非特殊领域，大部分算法的作用极其有限。
工程中更多时候需要的更高的视野，比如可能吭哧半天用算法提升了不到一倍的性能，其实如果从数据源下手优化，直接就是几个数量级的差距。
还有的时候，看似用算法优化了性能，但是代码却失去了可读性和扩展性，最后变得一团糟，要持续付出几倍的精力成本 debug 那些“算法”。
窃以为，工程思维和大局观比考算法有意义得多。

[kaf]

如果能仔细理解算法不知道复杂度还可以理解吧，如果算法本身不理解还说不出来就不太行，面试主要还是考察一个候选人的理解力，也不用单纯纠结会不会某个概念的问题

[Huelse]

而且要刷人还可以问个问题，该算法中 logn 是以什么为底？相信很少很少有人能回答上来

[FYFX]

@Huelse
快排每次以 pivot 分两部分所以是 2 为底，不过这不是不重要吗，反正换个底都能提个常数出来

[LaTero]

@Huelse 属于是数学基础不行了，O(n)和 O(2n)有区别？

[idrawer]

@lzgshsj 不写有办法吗？大环境不就是反向驱逐老实人

[MoYi123]

@Huelse 按大 O 表示法, 可以是任意常数为底.

[Karlven]

不正常

[hxysnail]

@microxiaoxiao 不影响调用不对吧？调用开销多少还是要心里有数的，有些场景一乱调就是故障

[microxiaoxiao]

@hxysnail 真不影响。就比如你调用文件系统，如果是别人给你的分布式文件系统，要是它卡了你找他就行了，你也评估不了它的代码复杂度呀。本身就是一个黑盒子。

[dabaibai]

写逻辑 5 年的话 不知道很正常。

[0zero0]

平时不记得是正常的，绝大多数开发的日常工作用不到这些，之前学校学的那些早忘了；
但是如果是准备面试，尤其面的**不是中高端岗位**的，那有些内容和知识点还是要补一补的。

[FrankHB]

@changnet ？不知道这种复杂度是怎么好意思占着后端的坑摸代码的？你当你茄子啊？（人策划都不见得敢那么划水、、、）
看来比 OP 这个应聘者还虎啊，现场瞎蒙都省了？

@lululau 问就是“算法”对实际开发本来就并没卵用，偏偏还很多人吹……实际上其中硬要有点卵用，那么最容易的恰恰就是对常见的复杂度的印象，因为好歹能帮助快速选型别墨迹着犯傻。
如果这点捡垃圾的价值都没有，直接写清楚“我不会工程需要的任何算法知识”，别骗人取乐。

@witcat 那么浪费人时间拉仇恨是哪来嫌弃人背后念叨的底气的，武德充沛？

[FrankHB]

@microxiaoxiao 你哪来的“瓶颈一定不在我”的余裕？或者你就是一次性碉堡侠，让你调用一次必定卡？调用几次就卡几次，全然不对业务实现质量负责的是吧？

[FrankHB]

@lzgshsj 因为这问题水到一定程度了。正常来讲能长期摸得下去所谓后端需要的代码（反正不会是能把复杂度包袱卸完的纯声明式语言写的）的人，就算完全没有复杂度的概念，也会对几个重要复杂度类之间的区别直觉上有反应，要有瓶颈就是他们不知道 /发明不出来大 O 记号的严格定义罢了。
但现在这人是至少打算表现出知道 O 那么回事的。所以要么是脑子实在迟钝真不适合碰后端代码，要么就根本是死记硬背半吊子，态度就不适合这类工作。

其实也就是现在语言花样多了才能那么容易蒙混过关。古早没所谓结构化编程的时候，混的下去的基本都是自己会发明栈帧之类的过程调用的实现的，否则写起代码来自己都能给自己烦死（特别是对照别人已经能自己发明出不那么烦的东西了）。
某种意义上，现在“写逻辑”当借口被滥用多了，也慢慢像是这种少根筋低效低能的贬义词了。

[unregister]

他不清楚，好的面试官应该和他解释一下，而不是在这里指责别人

[changnet]

@FrankHB 面试说不出这种复杂怎么就不好意思占着后端的坑了？知道有复杂度这个东西，知道有这个算法，用到的时候不会去查一下或者调一下现有的接口吗？这么多种排序，这么多种数据结构，这么多算法，难道平时用不上，都要牢牢记着？对应聘者而言，他是不知道你要问什么的，那要么他所有都死记硬背，要么他能灵活应用，我认为能灵活应用的人更适合，这有什么问题？

说句题外话，随便走进一家公司，到写代码的程序员面前去问，看看有几个能答上来

[wdhwg001]

我觉得这种问题都可以算是

宫廷玉液酒
一百八一杯

我们的口号是
没有蛀牙

这种程度的东西了，属于得了老年痴呆都不一定能忘掉的范畴，是在坟前喊一句“有 O(logN)的排序了”都能看到我掀开棺材板要见见世面的程度。

结果 V2EX 居然还有人需要去网上找找？

又不是让你手写快排，手写快排忘了还情有可原，快排是 O(N)到最坏 O(N²)平均 O(NlogN)都能忘真的不需要再补几年基础功再写代码吗，任何一个项目里有不知道 big O 是啥的人都是灾难性的隐患吧。

[FrankHB]

@changnet 你需要清楚，我没有说需要准备大量不确定的题的答案。这种问题质的评价，就是因为 OP 直接出的最水的一类的几乎没法更水的送分题（比较排序 naive(O^2)不 naive 的平均 O(n log n)），甚至因为结论过于容易被人死记硬背，而被许多人直球认为没资格做面试题。直接按这题的结果拒掉人，不太会怕误伤（至少比卡学历靠谱）。
如果这个层次的问题都要排除掉，那么算法差不多整个就不用问了（于是这人“熟练算法”也白写了，gg ）。

你提出“这么多种”×3 ，说明你对这个入门领域的问题层次以及难度梯度也是几乎毫无感知，所以才会把差距离谱的不同要求混为一谈。
对一般开发者来说，这里的结论完全不需要刻意记。稍微瞄过点算法入门的，都知道排序的平均复杂度形式上实在“正常”得过分，基本就 O(n^2)和 O(n log n)这两个答案二选一。因此甚至都不需要知道快速排序是个啥算法，这名字一听就不 naive ，所以是 O(n log n)。
退一步讲，现场“常识”就能推断出比较排序下限不可能少于 O(n)，掰指头算个 C(n,2)就该知道 naive O(n^2)，然后中间补个最常见的 log 而已。除了 O 本身的定义，就是高中数学（甚至……小学奥数）。这很难吗？
（排序默认都指时间复杂度，空间另说，稍微没那么水。）
你之前有提出要求理解算法的“效率”。对渐进复杂度这么容易复读（不刻意背就自觉记住）的形式都不去强调的话，如何去要人理解更普遍抽象或实际更妖孽的问题（比如卡常）呢？
你所谓的灵活应用字面上就比这里的问题实在难了不知道几个层次。

对职业开发者来说，见识少还是一层问题，还容易学习培训弥补，而少根筋是更劝退的。
比如上面有人说调用别人东西不要在乎这种问题，这是完全忽略了他的用户（可能是最终用户，可能是调用他的工作的开发者）的感受——他觉得锅全是他调用的，所以不管，顺手当做不存在实际直接甩给用户了。用户：exm ？？？

[microxiaoxiao]

@FrankHB 下次发表自己逻辑的时候别捎带我哈，看不懂你在说啥，还是说自是自身情绪的表达。

[hxysnail]

@microxiaoxiao 你评估不到不意味着没影响，这时应该拉能够评估的人一起评估吧？另外，举一个你评估不到的例子没有说服力吧？

我举个更贴切的例子：很多年前还在写 Python 时，有人判断一个 key 是否在一个字典 d 里面是这样写的：key in d.keys() 。d.keys() 会返回一个包含字典所有 key 的列表，因此判断变成一个 O(n)操作；而 Python 字典本身是哈希表，正常 O(1)时间可以完成判断的，但要这样写：key in d 。当前者将将 O(1)操作变成 O(n)，导致数据处理很慢，消息队列经常堆积。按你的说法，这时应该找 Python 的作者？

还有人在 list 头部插入，list 是动态数组，头部插入效率很慢，要挪动后面的所有元素，这些常识调用前应该都要心里有数吧？若能做到心里有数，才有意识去探索更科学的解决方案：比如用 deque 双向队列这样的数据结构。

其实这个问题的答案不用讨论，就是不正常。不影响调用不是不学无术的理由。何况读了这么多年书，精益求精的道理应该都听过吧？可学可不学难道等于不学？这样高度有点低了。

[STtree]

其实我觉得他这还不如说忘了快速排序的实现了，一个完全不会算复杂度的开发很有可能会埋下性能的坑。

[microxiaoxiao]

@hxysnail 看起来你没有太理解我表达的意思。我的完整意思是，每个人都无法穷尽所有细节，。如果一个人他关注的就是业务层面的，可能只要整体性能符合预期就行了，不符合再去分析瓶颈部分。你举的例子是建立在你相对熟练掌握下层细节的逻辑上。就以你这个例子再深入一点，系统层面调度也会对他有影响，是不是分时系统还是实时系统，还是古老的批处理，底层的硬件其实也会对软件有影响。就比如你的资源分配在寄存器和内存。系统分层次有个好处就在于屏蔽细节

[hxysnail]

@microxiaoxiao 所以这些都是要关注的呀，只是不用自己实现而已。掌握这些底层原理的好处就是写代码不容易给别人挖坑，不然调用出问题还不得人去解决？做底层的工程师一定不会帮你做上传的业务工程师解决的呀

[hxysnail]

我本人面试也比较喜欢聊数据结构和算法，倒不是想招个人进来写这些基础的东西，主要是想评估：

1. 候选人的逻辑思维能力如何？人是否聪明？
2. 候选人的编程能力如何？

一个连最基本的排序算法都玩不明白的人，你指望他干啥呢？只能干点调调接口，调调包的美其名曰业务开发吧？
一个连基本的排序算法都写不出来的人，你指望他能写啥代码呢？有啥堆啥吧？调通就了事吧？

当年在 BAT 做招聘，别说一个工作 5 年的后端开发，就是一个校招实习生，排序算法答不明白都是直接让 go home ，其他的都不用聊。

[Rooger]

@unregister 抱歉让你感觉我在指责别人了，我说了这是我的困惑。没有指责候选的任何意图，可能我表达的不准确。

[e7]

@shunia 比较排序的极限是 O(n*logn)，但快排最坏是 O(n^2)，还有最坏也是 O(n*logn)的算法

[Dogtler]

熟练算法跟数据结构这个 LeetCode 得刷够一定的量 才有勇气这么简历上写，简历第一印象 应该是把自己擅长的展示出来，求职者这么写的话实在是相当不明智，侧面估计也是为了简历不被 PASS 把，毕竟寒气已经传给每一个码农了。

@xsen 老哥说的对，文人相轻 码农之间的鄙视链一直都是，其实在老板眼里 就是个工具人 价值榨干就 35 劝退。后端的话，算法讲道理 也就是面试之前刷一刷，满足一下面试的形式主义 过场，毕竟谁都知道正式上班都是拧螺丝。

[xsen]

@hxysnail #147 搞笑，不妨这位大佬数数您工作这么多年项目中写了几个排序算法——只是单纯好奇

反正本人面试中从来不问数据结构和算法，就单纯的聊基础、项目与工程化。看重学习能力、意向、沟通能力，如果一个人连事情都说不明白，还谈何逻辑能力

[xsen]

不就是为了卡人而已嘛，还非得说的那么冠冕堂皇。国内又有多少岗位是深入涉及到算法的

[FrankHB]

@changnet 你之前的公然扯蛋，已经有些涉嫌侮辱业界和消费者智商了。路人还没资格反对你的观点了不是？
你再看看到底这里几个人不同意你的观点？你能以看不懂我说的搪塞，还能一个个全塞抹布过去？

给类似捧臭脚的：
做业务就做业务，不会写代码的就不要给写代码的捣乱。非得强行全栈的别指望好下场。
业界常识：这些工作之间互相不可替代。你可以不会其中一项，但是不会的活就得别人做。要么老实全当碉堡侠，剩下的相当于外包出去了。
再者，没被市场淘汰和正在被淘汰的厂，哪来那么空给在这种层次的问题上浪费时间“查接口”来糊弄。（我是有些奇怪有些厂不给加班费的超量工时是不是就是专预备给这种活了……）
退一步讲，作为专业人员，就是要有合理理由自认为“不会”，那也该直接按不合理需求怼回去。自己先怂了，达不到对方期望的这类岗位的一般常识性的要求，怪谁？

[FrankHB]

不好意思，上面 at 错了。上面应该 @microxiaoxiao 。不过下面一段通用。

[microxiaoxiao]

@FrankHB 假期还搁这扯鸡巴呢，大晚上的。你反对就反对呗，多厉害似的。子写的多就有水平嘛？老子道德经五千字，嘻嘻

[microxiaoxiao]

@FrankHB 你自己开个贴不香嘛，@那么多人有谁啥卵用，希望得到陌生人认可吗？我很认可你哟，嘿嘿，吊毛。还公然侮辱，天天在这扯什么大旗，吓唬谁呢，也要看你值得不值得呀。看我回复一般人怎么回复的，再来和我逼逼

[hxysnail]

@xsen 麻烦看清楚再回复，我说过了“倒不是想招个人进来写这些基础的东西”，做工程一定是站在巨人的肩膀上，调用成熟的解决方案，但这不代表工程师不需要懂

[hxysnail]

@xsen 我不知道你是不是想说“数据结构算法无用论”，合着大学的课都是开着玩的？那么多大厂面试都是问着玩儿？不过无所谓，你我可以保持自己的观点，不同而已。

[hxysnail]

@xsen 说“卡人”就没依据了。站在面试官的角度，巴不得每个候选人都合格，这样花在招聘的时间最少。别人怎么想我不清楚，但至少我个人是这样。有时面了好多，但都没有遇到合适的，是有挫败感的。

另外，确实大部分岗位都是不需要深入涉及算法的。但您可能对深入有点误解，排序算法应该只是极浅的算法吧。常用的那些数据结构，也是很基础的吧。

[xsen]

@FrankHB #136 确定瓶颈开始的做法从来都不是调用几次或者评估某个算法的实践复杂度
似乎您连压测都不知道

[xsen]

@hxysnail #157/158/159 若您有注意我的观点，我看重其中一点就是学习能力；其实就是两种做法，一个是我我这样的我会想办法评估面试者的学习能力与意向，因为只要我确定这一点，就可以肯定这个面试者对不太高精尖的算法随时都可以学习、掌握然后应用，配合压测自然可以进一步优化算法

数据结构算法对国内的绝大多数跟风问的公司来说确实没啥用，因为比较工作涉及算法的也就小部分的职位。招聘从来都不是招最好的，而是要根据自己的需要寻求合适的人

对于站在面试官的角度，从概率来说大多数确实都是为了单纯卡人而已。巴不得每个候选者都合格，这本来就不现实

对于做 IT 的来说，相当部分人没有丝毫的统计与概率学的概念——这个真的很违反常识，毕竟又不是没学过概率统计

[hxysnail]

@xsen 实际上，我不太理解你的观点是什么。不过，想办法评估面试者的学习能力，确认学习能力 ok ，可以随时学习上手倒是没毛病。

[xsen]

@hxysnail #162 其实我的出发点非常简单，除非我确定需要个算法工程师，不然我是不会问算法
因为相对算法来说，别的方面我更为关注——相对来说招进来更符合我的实际需求。对于简单的算法，有学习能力的人要掌握快也不过半天的时间

我需要的是能切实给我的工作带来实际效果的人，所以我更关注学习能力、意向、项目经验、工程化能力等

[hxysnail]

@xsen 但是你要明白，你关注的这些东西，跟他的计算机基础是强相关的。这才是面试考察计算机基础的原因，而数据结构算法是其中比较重要的部分。关注学习能力没有错，但知识面也是很重要的一个因素，决定一个人有没有学习意识。打个比方，如果一个人完全不知道数据结构和算法的存在，完全不懂不同的写法有不同的效率表现，他如何主动去学呢？正如我上面举的一个例子，没有数据结构算法观，写出来的程序虽然逻辑上是正确的，但处理速度却跟不上。虽然这样的场景不是每天都有，但也不是很罕见。另外，我还招过一些外包，看做的项目好像很丰富，但进来后发现连锁是什么都不知道，怎么指望他能做好代码临界区控制呢？学？首先要知道这个东西的存在？不然就是问题暴露出来之后再亡羊补牢。最后，我认同学习能力、意向、项目经验、工程化能力这些都是考察的重点。只不过我觉得基础也很重要，数据结构和算法也是其中比较重要的组成部分。

[FrankHB]

@microxiaoxiao 你缺啥提啥我不拦着，不过给我单独一楼 at 一次算你祖坟冒青烟的机缘都不要，那就当做欠一次好了。
陌生人？你想多了，祈祷别在业界拉屎的时候被人逮到就好。
@xsen 别多想，就凭你对“瓶颈”的描述，正常情况下你应当没权分配所谓压测的职位和相关资源。
若你所在的组织不幸地把这种事务浪费在你这位置上，只能祝你们好运。

[microxiaoxiao]

@FrankHB 你这种小杂毛真的是，水平不咋地，还喜欢唧唧歪歪。我学复杂度的时候估计你还在穿裤衩子。还天天业界，给你一个 IO 异常，你估计都分析不出哪儿卡了。

[microxiaoxiao]

@FrankHB 哦 对了 下次代表业界的时候拜托说具体点。是前端，是后端，是存储，是流媒体，是数据库，是本地文件系统还是分布式网络的？别他妈一天天搁我这装。你能代表你嘛币呢？

[FrankHB]

@microxiaoxiao 你这废话对谁都没什么用，正常情况到底谁是杂毛自己最清楚。
但是还得多吊一下你的阅读理解水平就挺杂毛的。
代表？我需要代表什么了？搁你这？你谁啊，配我去理解你这和别的地方有什么不同？
说到底，你什么时候产生你配浪费特定的谁的时间被收拾的错觉了？虽然观点行事颇为腌臜，你也没到人人得而诛之的斤两吧，所以被收拾也是随缘的事。就是愿意求仁得仁的，我还不愿意普渡众生呢，何况你这种没礼（脑）貌（子）读不懂空气的。