以图明志

计算机算法

[专题] 快速排序里的学问:从猜数字开始

猜数字里的算法思想
我们先来玩一个猜数字游戏:我心里默念一个1~64之间的数,你来猜(你只能问答案是“是”或“否”的问题)。为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?很显然,二分。先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。

计算机算法

[专题] 快速排序里的学问:再看看称球问题

根据问题选择N分法
12个小球,其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。这个问题是一道流传已久的智力题。网络上也有很多讲解,还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了,只能一个个方法试,然后看看哪种方案最少。

计算机算法

[专题] 快速排序里的学问:信息熵

从信息熵角度去理解问题
信息是个很抽象的概念。人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说,我们要搞清楚一件非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。

计算机算法

[专题] 编程之美2.3笔记:寻找发帖“水王”

降低问题规模的思想
抽象就是从问题中提取有用的,本质的特征,然后将问题用一个简洁但包含同样信息的模型表示出来。复杂的问题经抽象后,可能会变成一个简单的问题,也可能会变成一个曾经遇到的问题,当然也可能仍然是复杂的问题。不管抽象后得到的结果是哪一种,看着抽象后的问题,想出解的可能性必然比直接看原题想的可能性大。

计算机算法

[专题] 快速排序里的学问:快速排序的过程

理解快速排序的工作机制
通过前面问题以及引入了“信息熵”的概念,我们可以重新来理解排序的本质:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句。

计算机算法

[专题] 快速排序里的学问:霍尔与快速排序

再次深入理解快速排序
霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家,他是著名的快速排序 (QuickSort) 的发明者。在平均状况下,排序 n 个项目要Ο(n log n) 次比较,而且通常明显比其他Ο(n log n) 演算法更快。所以它是一个被广泛使用的算法。在一次采访中,霍尔谈到了发明这个算法的背景。

计算机算法

[专题] 快速排序里的学问:霍尔快排的实现

霍尔快排的C语言实现
专题的前一篇讲了快速排序的始祖——霍尔快排,那么这里就简单地实现以下霍尔快排。补充说明下,快排的一个核心步骤是选取枢纽元,通常的做法是将第一个元素用作枢纽元,《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。排序的思路是,选定一个枢纽元,比枢纽元大的全部丢到右边,比枢纽元小的全部丢到左边。

计算机算法

[专题] 快速排序里的学问:枢纽元选择与算法效率

枢纽元选择也有学问
通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。如果输入是随机的,那么这是可以接受的,但是如果输入是预排序的或者是反序的,那么这样的枢纽元就产生一个劣质的分割,因为所有的元素不是被划入S1就是被划入S2。更有甚者,这种情况发生在所有的递归调用中。

计算机算法

[专题] 快速排序里的学问:随机化快排

选择随机数作为枢纽元
一般来说随机选取枢纽元这种策略非常安全,除非随机数生成器有问题(这不像你所想象的那么罕见),因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。算法与前面《算法导论》里的例子差不多,只是在调用分割Partition时加入一个随机数,具体可以参看程序。

互联网时代

为什么互联网产品创业成功率不足1%?

能活下去就已经很不容易了
众所周知,互联网新产品的成功率可能不足1%。不成功的产品勉强维持几年,终究还是会化为粉末。相当于互联网新产品的存活率可能不足1%。讲这件事,首先得对成功产品下一个定义:譬如有独特的品牌价值,有相当大的用户量,以及可靠的盈利模式。没错,能达到标准的不足1%,别的都只不过是炮灰。
1 / 1 首页 < Prev 1 Next > 尾页 页码: