PHP 进阶

算法
漫谈递归：尾递归与CPS

与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。 ... [详细]

2014-05-16 11:47:12
算法
漫谈递归：补充一些Continuation的知识

Continuation是一种非常古老的程序结构，简单说来就是entiredefaultfutureofacomputation,即对程序“接下来要做的事情”所进行的一种建模，即为“完成某件事情”之后“还需要做的事情”。而这种做法，也可以体现在尾递归构造中。在函数式语言中，continuation的引入是非常自然的过程 ... [详细]

2014-05-16 11:47:12
算法
漫谈递归：PHP里的尾递归及其优化

事实证明，尾递归在php中是没有任何优化效果的。一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的，即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化，比如C语言对尾递归的优化。 ... [详细]

2014-05-16 11:47:12
算法
漫谈递归：从汇编看尾递归的优化

对于尾递归，很多人的理解仅局限于它是递归和尾调用的一个合体，比普通递归效率高。至于效率为什么高，高在哪，可能没有深究过。在执行函数B时，函数A的栈帧其实是已经大部分没用了，可以被修改或覆盖。编译器可以利用这一点进行优化，函数B执行后直接返回到函数A的调用者。 ... [详细]

2014-05-16 11:47:12
算法
SICP：费马小定理与素数检测

我知道费马等一些人都热衷于“纯数学”，那些被看起来毫无实用价值的“纯理论”，可这费马检查，却是全世界的服务器每秒中都要运行无数次的RSA算法的理论基石。就我自己而言，每天使用SSH的时候都要用到。而几位科学家把这这一切联系起来的过程，实在称得上是“玄妙”了。 ... [详细]

2014-05-16 11:47:12
算法
快速排序里的学问：从猜数字开始

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

2014-05-16 11:47:12
算法
快速排序里的学问：再看看称球问题

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

2014-05-16 11:47:12
算法
快速排序里的学问：信息熵

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

2014-05-16 11:47:12
算法
编程之美2.3笔记：寻找发帖“水王”

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

2014-05-16 11:47:12
算法
快速排序里的学问：快速排序的过程

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

2014-05-16 11:47:12
算法
快速排序里的学问：霍尔与快速排序

霍尔(SirCharlesAntonyRichardHoare)是一位英国计算机科学家，他是著名的快速排序(QuickSort)的发明者。在平均状况下，排序n个项目要Ο(nlogn)次比较，而且通常明显比其他Ο(nlogn)演算法更快。所以它是一个被广泛使用的算法。在一次采访中，霍尔谈到了发明这个算法的背景。 ... [详细]

2014-05-16 11:47:12
算法
快速排序里的学问：霍尔快排的实现

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

2014-05-16 11:47:12

扫码关注 PHP1 官方微信号

Tools Online | 在线开发工具

RankList | 热门文章

Recommend | 推荐阅读

网站首页

PHP资讯

PHP教程

服务器技术

数据库

前端开发

视频教程

MySql

PHP问答

开发工具

PHP安全

大话程序猿

职场

PHP 进阶

漫谈递归：尾递归与CPS

漫谈递归：补充一些Continuation的知识

漫谈递归：PHP里的尾递归及其优化

漫谈递归：从汇编看尾递归的优化

SICP：费马小定理与素数检测

快速排序里的学问：从猜数字开始

快速排序里的学问：再看看称球问题

快速排序里的学问：信息熵

编程之美2.3笔记：寻找发帖“水王”

快速排序里的学问：快速排序的过程

快速排序里的学问：霍尔与快速排序

快速排序里的学问：霍尔快排的实现