P180. 快乐数

https://algocasts.io/episodes/6emEKnpV

老师,我看见相同级别时间复杂度的算法效率差别挺明显的,但计算常数项好像也比较困难,选用算法可以怎样做比较和取舍呢?

@yipwinghong

这个问题分两种场景讨论。

第一,在面试中解算法题。这种一般来说直接看数量级就行,也就是分析出算法的时间复杂度,O(1) 优于 O(log(n)) 优于 O(n) 优于 O(n*log(n)) 优于 O(n^2) … 一般来说,面试官不会再去让你分析 O(c*n+k) 和 O(n*log(n)) 在 n 取什么值时,选其中一种算法要优于另一种算法。面试中,大部分时候关注数量级,也就是大 O 表示即可。

第二,在工作中遇到算法选择。这种分析常数项时间复杂度往往更有意义,因为更高效意味着可以省下更多钱,或者赚来更多钱。但是,这也不是说任何时候都一上来就比较可选的所有算法,选最快那个。这种就有点走向另一个极端了。工作中最终算法的选择(技术选型/架构方案选择也一样),都是要综合考虑可读性和可维护性,再结合业务实际的数据特点,去做选择。基于这一点,一般来说,先用最容易理解最容易维护的那个版本。在不影响可读性和可维护性的前提下,再根据业务实际数据特点,去做优化。比如,在某个业务中,要排序大量的(比如 14 亿)年龄数据,那选用计数排序显然是比使用通用排序更好的。

最后,如果有几个可选算法的可读性和可维护性看起来差不多(其它可能的指标也差不多),算法时间复杂度数量级也是一样的,那可以对它们做 benchmark。产生一些符合具体业务数据特点的数据,然后实际跑一下,看哪个算法快一些。

写着写着突然想起已故 Erlang 之父 Joe Armstrong 说过的一段话,送给看到这篇帖子的人:

Make it work, then make it beautiful, then if you really, really have to, make it fast. 90% of the time, if you make it beautiful, it will already be fast. So really, just make it beautiful! — Joe Armstrong

以上的话,无论是对于编写算法、开发软件、架构系统,我觉得都适用。

感谢~(虽然我水平远没达到要考虑这个的程度,只是好奇想了解一下)
所以还是尽量每种方法都掌握吧。:joy: