Veda 原型
成功，唯有积累，没有奇迹
计算机算法
[专题] 快速排序里的学问：随机化快排
选择随机数作为枢纽元
在 2012年12月12日 那天写的
31,694 views
一般来说随机选取枢纽元这种策略非常安全，除非随机数生成器有问题（这不像你所想象的那么罕见），因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面，随机数的生成一般是昂贵的，根本减少不了算法其余部分的平均运行时间。算法与前面《算法导论》里的例子差不多，只是在调用分割Partition时加入一个随机数，具体可以参看程序。
计算机算法
[专题] 快速排序里的学问：枢纽元选择与算法效率
枢纽元选择也有学问
在 2012年12月11日 那天写的
22,842 views
通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。如果输入是随机的，那么这是可以接受的，但是如果输入是预排序的或者是反序的，那么这样的枢纽元就产生一个劣质的分割，因为所有的元素不是被划入S1就是被划入S2。更有甚者，这种情况发生在所有的递归调用中。
计算机算法
[专题] 快速排序里的学问：霍尔快排的实现
霍尔快排的C语言实现
在 2012年12月10日 那天写的
23,623 views
专题的前一篇讲了快速排序的始祖——霍尔快排，那么这里就简单地实现以下霍尔快排。补充说明下，快排的一个核心步骤是选取枢纽元，通常的做法是将第一个元素用作枢纽元，《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。排序的思路是，选定一个枢纽元，比枢纽元大的全部丢到右边，比枢纽元小的全部丢到左边。
计算机算法
[专题] 快速排序里的学问：霍尔与快速排序
再次深入理解快速排序
在 2012年12月08日 那天写的
27,951 views
霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家，他是著名的快速排序 (QuickSort) 的发明者。在平均状况下，排序 n 个项目要Ο(n log n) 次比较，而且通常明显比其他Ο(n log n) 演算法更快。所以它是一个被广泛使用的算法。在一次采访中，霍尔谈到了发明这个算法的背景。
计算机算法
[专题] 快速排序里的学问：快速排序的过程
理解快速排序的工作机制
在 2012年12月06日 那天写的
25,622 views
通过前面问题以及引入了“信息熵”的概念，我们可以重新来理解排序的本质：一组未排序的N个数字，它们一共有N!种重排，其中只有一种排列是满足题意的（譬如从大到小排列）。换句话说，排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”，这就相当于猜数字游戏里面的一个问句。
计算机算法
[专题] 编程之美2.3笔记：寻找发帖“水王”
降低问题规模的思想
在 2012年12月05日 那天写的
20,433 views
抽象就是从问题中提取有用的，本质的特征，然后将问题用一个简洁但包含同样信息的模型表示出来。复杂的问题经抽象后，可能会变成一个简单的问题，也可能会变成一个曾经遇到的问题，当然也可能仍然是复杂的问题。不管抽象后得到的结果是哪一种，看着抽象后的问题，想出解的可能性必然比直接看原题想的可能性大。
计算机算法
[专题] 快速排序里的学问：信息熵
从信息熵角度去理解问题
在 2012年12月04日 那天写的
16,163 views
信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。
计算机算法
[专题] 快速排序里的学问：再看看称球问题
根据问题选择N分法
在 2012年12月03日 那天写的
15,006 views
12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。这个问题是一道流传已久的智力题。网络上也有很多讲解，还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了，只能一个个方法试，然后看看哪种方案最少。
计算机算法
[专题] 快速排序里的学问：从猜数字开始
猜数字里的算法思想
在 2012年12月02日 那天写的
20,320 views
我们先来玩一个猜数字游戏：我心里默念一个1~64之间的数，你来猜（你只能问答案是“是”或“否”的问题）。为了保证不论在什么情况下都能以尽量少的次数猜中，你应该采取什么策略呢？很显然，二分。先是猜是不是位于1~32之间，排除掉一半可能性，然后对区间继续二分。
计算机算法
SICP：费马小定理与素数检测
费马小定理是数论的基础理论之一
在 2012年11月05日 那天写的
22,757 views
我知道费马等一些人都热衷于“纯数学”，那些被看起来毫无实用价值的“纯理论”，可这费马检查，却是全世界的服务器每秒中都要运行无数次的 RSA 算法的理论基石。就我自己而言，每天使用 SSH 的时候都要用到。而几位科学家把这这一切联系起来的过程，实在称得上是“玄妙”了。
计算机算法
[专题] 漫谈递归：从汇编看尾递归的优化
尾递归的编译器优化
在 2012年10月18日 那天写的
20,930 views
对于尾递归，很多人的理解仅局限于它是递归和尾调用的一个合体，比普通递归效率高。至于效率为什么高，高在哪，可能没有深究过。 在执行函数B时，函数A的栈帧其实是已经大部分没用了，可以被修改或覆盖。编译器可以利用这一点进行优化，函数B执行后直接返回到函数A的调用者。
计算机算法
[专题] 漫谈递归：PHP里的尾递归及其优化
PHP编译器没有对尾递归进行优化
在 2012年10月17日 那天写的
25,496 views
事实证明，尾递归在php中是没有任何优化效果的。一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的，即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化，比如C语言对尾递归的优化。
计算机算法
[专题] 漫谈递归：补充一些Continuation的知识
Continuation在函数式编程是非常自然的
在 2012年10月15日 那天写的
14,179 views
Continuation是一种非常古老的程序结构，简单说来就是entire default future of a computation, 即对程序“接下来要做的事情”所进行的一种建模，即为“完成某件事情”之后“还需要做的事情”。而这种做法，也可以体现在尾递归构造中。在函数式语言中，continuation的引入是非常自然的过程。
计算机算法
[专题] 漫谈递归：尾递归与CPS
尾递归就是Continuation Passing Style
在 2012年10月14日 那天写的
23,659 views
与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。
计算机算法
[专题] 漫谈递归：从斐波那契开始了解尾递归
对尾递归的大概了解
在 2012年10月12日 那天写的
45,207 views
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。
计算机算法
[专题] 漫谈递归：循环与迭代是一回事吗？
理清递归、迭代、循环的概念
在 2012年10月10日 那天写的
64,159 views
迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。个人认为迭代是循环的一种，循环体代码分为固定循环体，和变化的循环体。
