Fork me on GitHub

算法

归并排序中对小数组采用插入排序

纯归并排序的复杂度为O(nlgn),而纯插入排序的时间复杂度为O(n^2)。数据量很大的时候采用归并排序。 但是在n较小的时候插入排序可能运行的会更快点。因此在归并排序中当子问题变得足够小时, 采用插入排序来使得递归的叶子变粗可以加快排序速度。那么这个足够小到底怎么去衡量呢? 请看下面: 这么几个我不证明了,比较简单: 插入排序最坏情况下可以在O(nk)时间内排序每个长度为k的n/k个子列表 在最坏情况下可在O(nlg(n/k))的时间内合并这些子表 修订后的算法的最...

海盗分金

海盗,大家听说过吧。这是一帮亡命之徒,在海上抢人钱财,夺人性命,干的是刀头上舔血的营生。在我们的印象中,他们一般都瞎一只眼,用条黑布或者讲究点的 用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯,而且总要画上一张藏宝图,以方便后人掘取。不过大家是否知道,他们是世界上最民主的团体。参加海盗 的都是桀骜不驯的汉子,是不愿听人命令的,船上平时一切事都由投票解决。船长的唯一特权,是有自己的一套餐具——可是在他不用时,其他海盗是可以借来用 的。船上的唯一惩罚,就是被丢到海里去喂...

快速排序和二分查找

排序算法中最快的是快速排序算法,搜索算法中最快的是二分搜索算法。我也最喜欢这2 个算法。 因为它们是使用递归实现的,代码简洁清晰,效率又非常高。 根据我的理解,算法的本质就是数学。根据输入和设定的目标,采用有限的步骤实现输出。 通常,使用计算机实现的算法,都会用到循环,这样才能发挥计算机高速运算的优势。 循环和递归是等效的,这已经被科学家所证明。数学上没有循环,只有递归的概念,因此使用递归代替循环表示算法有很多好处: 递归的代码要比循环简洁很多,也优雅很多。 递归的代...

回溯法解决八皇后问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后, 使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。 当且仅当n = 1或n ≥ 4时问题有解 — 摘自八皇后问题wiki 利用回溯法解决# coding: utf-8 __author__ = 'Administrator'...

利用递归算法并行化解决谜题框架

我们将谜题定义为:包含一个初始位置,一个目标位置,以及用于判断是否是有效移动的规则集。 规则集包含两部分:计算从指定位置开始的所有合法移动,以及每次移动的结果位置。 Java抽象下面先给出表示谜题的抽象类,其中的类型参数P和M表示位置类和移动类。根据这个接口, 我们可以写一个简单的串行求解程序,该程序将在谜题空间Puzzle Space中查找, 直到找到一个解答或者找遍了整个空间都没有发现答案。注:一个移动M代表一步 /** 表示 搬箱子 之类谜题的抽象类*/ publ...