黑客与画家

编程是一种艺术创作

为什么说任何基于比较的算法将5个元素排序都需要7次?

原文链接:http://justjavac.com/other/2013/04/10/why-any-sort-algorithm-based-on-the-comparison-of-the-five-elements-are-needed-7-times.html 排序算法对结果的唯一要求就是操作数满足全序关系: 如果 a≤b 并且 b≤c 那么 a≤c(传递性)。 对于 a 或 b,要不 a≤b,要不 b≤a(完全性)。 这个问题可以用信息论来回答。 我从 1 到 5 中挑一个数字出来让你来猜,每回合你都可以问我一个问题,我的回答“是”或“不是”(1 或 0),那么你至少需要几个回合才能保证猜出这个数字? 比较符合这个游戏精神的玩法是从自己的幸运数字(比如我的是7)开始猜起,一个一个地问我“是不是X?”, 可能你的运气足够好,一个回合就能够猜对,但是在最坏的情况下可能就需要5个回合,所以你的答案应该是“至少需要5个回合” (事实上你至少只需要一次就“有可能”猜出来,但为了“保证能”猜出来,你只好委曲求全地说 5), 换句话说这种猜法的最优下界是 5。 (平均性能是 1×1/5+2×1/5+…+5×1/5=(1+…+5)/5 = 3) 但因为你会二分,所以会这样问“是不是比3大?”……而且无论我挑出的数字是几,都只用3个回合。 二分显然是一种更佳的策略,那么它好在什么地方呢? 用信息论理解: 最大的熵。 英文版维基百科词条有个大致的解释:Comparison_sort, 最少次数为 log(5!) = 6.91,取整的话,就是 7。 决策树如下: 如果我们用归并排序的话,比较次数是O(nlogn),因为归并排序是 全局最优解,但是在局部,归并并不都保证是最优的。 附一张快速排序的 gif 图:

算法设计师成新宠

Aisle50公司共同创建人Christopher Steiner,在其新著中统计了数字取得统治地位的多种方式。他说:“当今社会上谁的机会最大?是开发人员”。 35岁的Christopher Steiner是Y Combinator资助的创新公司Aisle50的共同创始人之一,Aisle50公司经营网上杂货店交易。他的新著《自动化:算法是如何一统天下的》明天开售。他最初计划只专注于写华尔街。他说:“可爆料的故事多多,又发生了‘闪电崩盘’。但过了一阵子我想:大家真那么关心上世纪九十年代13种不同的电子培训网络吗?”。结果,这位前技术记者扩展了研究范围,探讨算法的力量如何已经远远超出了华尔街、接触到了我们每一个人。先从今天的弄潮儿谈起。

二分查找法的实现和应用(进阶篇)

在《二分查找法的实现和应用汇总》中,我介绍了二分查找法的基本应用,不过在面试的准备过程中,我还碰到了更多对于二分查找法的更进一步的使用。其实在《二分查找法的实现和应用汇总》的最后,我已经介绍了一个非常规的使用,也就是基于“轮转后的有序数组(Rotated Sorted Array)”检查某一个数是否存在。

LinkedIn账户密码泄露,钓鱼邮件蜂拥而至

由于LinkedIn用户多为“含金量”较高的职业人士,LinkedIn失窃的账户密码对于钓鱼邮件和网络不法分子来说格外具有吸引力。 本周三,知名专业社交网站LinkedIn爆出部分用户账户密码失窃,LinkedIn主管文森特·希尔维拉(Vicente Silveira)在其个人博客中证实了此事。根据Venturebeat的报道,650万被破解的LinkedIn账户密码列表已经被上传至一家俄罗斯黑客服务器(哈希加密非明文),但目前尚不能确认这是否是被破解账户的总数。