下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...... 约1204字，阅读全文
All posts about subject 算法
求平方根倒数的算法
Tags: 算法, 算法分析
算法百科全书 - Encyclopedia of Algorithms
Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。 翻了一下，...... 约368字，阅读全文
Tags: Encyclopedia of Algorithms, 算法
有序矩阵的中位数算法
给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...... 约842字，阅读全文
Tags: 中位数, 矩阵, 算法
Perfect Shuffle的算法
珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。 一年前，我们讨论过一个算法问题，perfect shuffle，...... 约1180字，阅读全文
Tags: memo, perfect shuffle, 算法, 面试题
素数筛法的复杂度
Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的...... 约1150字，阅读全文
Tags: 复杂度, 复杂性, 算法, 素数
编程的核心是数据结构，而不是算法
Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: 你无法断定程序会在什么地方耗费运...... 约769字，阅读全文
Tags: unix, 数据结构, 算法
图同构问题属于P？
更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。 提交论文到arxiv不需要审阅...... 约1152字，阅读全文
Tags: 图同构, 算法
魔方里的数学
今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学方法 :) 。 魔方的解法，在网上已...... 约1130字，阅读全文
Tags: Rubik's Cube, 图论, 洗牌, 算法, 解法, 魔方
一个算法面试题 & 面试题库
一个面试题，号称是微软的 输入$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$$，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为$$a_1, b_1, ..., a_n, b_n$$。 刚一...... 约896字，阅读全文
Tags: 算法, 面试, 题库
理论计算机初步：算法和计算模型
下面是wikipedia上算法的定义： 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算...... 约1902字，阅读全文
Tags: 模型, 理论计算机, 算法, 算法模型初步