TAOCP第三卷搜索算法中最先讲的就是顺序搜索。
顺序搜索的优点是足够的简单,在数据量足够小的时候速度最快。
而且在无序数据集的时候顺序搜索是唯一可行的方法。
首先是6.1节的程序S
int search(int array[],int count, int n) {
int i = 0;
for(; i < count; i++) {
if(array[i] == n) {
return i;
}
}
return -1;
}
非常简单,但是每个循环需要比较两次。
通过在尾部追加一个哨兵值,可以把比较次数降为一次。
这就是6.1节的算法Q:
int search(int array[],int count, int n) {
int i = 0;
int t = array[count]; //假设这里有空间,先保存现场
array[count] = n;
for(; array[i] != n; i++) {
}
array[count] = t; //还原现场
if(i < count) {
return i;
else {
return -1;
}
}
当n比较大的时候会比算法S快一些。但是要求在array的尾部有多余的空间,
内存分配的时候需要注意一点。
算法Q有个一个优化版Q'
int search(int array[],int count, int n) {
int i = 0;
int t = array[count];
array[count] = n;
while(1) {
if(array[i] == n) {
break;
}
if(array[i+1] == n) {
i++;
break;
}
i += 2
}
array[count] = t;
if(i < count) {
return i;
else {
return -1;
}
}
一次步进2,算是一种手工的循环展开吧。
不过gcc使用-O3参数时会自动进行循环展开,
这种工作还是留给编译器吧。
如果数据是有序的,则可以使用算法T:
int search(int array[],int count, int n) {
int i = 0;
int t = array[count];
array[count] = INT_MAX; //设置一个大于array中所有值的值
for(; array[i] < n; i++) {
}
array[count] = t;
//array[i] >= n
if(i < count && array[i] == n) { //多了一个判断条件
return i;
else {
return -1;
}
}
在查找成功的时候算法T和算法Q一样快,
但是失败的时候T比Q大约两倍。
对于有序数据可以使用更快的二分查找,
但是并不是所有的时候二分查找都跟快。
在数据总数N比较小的时候,算法T更快,而且T更简单。
分享到:
相关推荐
TAOCP作为一个资料库是绝对优秀的,基础的算法只要你能想到的,几乎都可以在上面找到原始出处。
TAOCP作为一个资料库是绝对优秀的,基础的算法只要你能想到的,几乎都可以在上面找到原始出处。
MMIX 手册(TAOCP第一卷中的相关部分)
TAOCP卷一
计算机程序设计艺术中文版清晰 43M 计算机程序设计艺术(第三卷).pdf
Addison Wesley - 2001 - Knuth - The Art of Computer Programming Vol I II III IV全卷共165MB.一共只要15分. 我也是下载后自行打包的.原来一共8卷,每个3分,用了我24分. 拿来共积分不多的人下载.
计算机程序设计技巧3.排序查找计算机程序设计技巧3.排序查找
TAOCP作为一个资料库是绝对优秀的,基础的算法只要你能想到的,几乎都可以在上面找到原始出处。
taocp-en-djvu
计算机程序设计艺术(第一卷)
计算机程序设计进阶必备,研究编程宝典,内容包含前三卷的英文版。
计算机程序设计艺术(第三版,英文版,第一卷:基本算法),TAOCP V1 3rd Edition,英文扫描版,清晰,带书签
TAOCP Errata TAOCP Errata TAOCP Errata TAOCP Errata TAOCP Errata
第一部分:Java开发入门 第二部分:Java语法基础 第三部分:Java核心编程 第四部分:Java图形编程 第五部分:Java网络编程
TAOCP, 算是到现在为止已经写出来的
这个不用多说了吧,7卷计算机编程艺术的数学基础。想看TAOCP的必看。
计算机程序设计艺术(第二卷)
最著名的算法分析书,作者是顶尖大牛,英文原版,第三版。
现在发行的只有三卷,分别为基础运算法则,半数值算法,以及排序和搜索(在写本文之际,第四卷已经出来了,我也在第一时间抢购了一本)。本书结合大量数学知识,分析不同应用领域中的各种算法,研究算法的复杂性,即...
mmix 文档,用于knuth编著的taocp。 可学习mmix汇编语言。