北京网站设计公司飞沐,刚刚传来最新消息,新手怎么引流推广,网站建设 问答查找#xff08;检索#xff09;#xff1a;
定义#xff1a;从给定的数据中找到对应的K 1#xff0c;顺序查找#xff1a;
O(n)的从前向后的遍历
2#xff0c;对半查找#xff0c;要求有序
从中间开始查找#xff0c;每次检查中间的是否正确#xff0c;不正确就…查找检索
定义从给定的数据中找到对应的K 1顺序查找
O(n)的从前向后的遍历
2对半查找要求有序
从中间开始查找每次检查中间的是否正确不正确就根据性质去左边or右边找 2.1对半插入排序
在找位置的时候是logn 去找 但是最后需要换位置 排序之后仍然是O()N^2) 对同一序列分别进行对半插入排序和直接插入排序两者之间
可能的不同之处是___D___。【考研题全国卷】
A.排序的总趟数
B.元素的移动次数
C.使用辅助空间的数量
D.元素的比较次数 2.2二叉判定树扩充二叉树
在二叉树中空指针的位置都增加特殊的结点空叶结点由此生成的二叉树称为扩充二叉树。称圆形结点为内结点方
形结点为外结点
➢当high-low1 £ 0时T(low, high)为空
➢当high-low1 0时令mid ë(lowhigh)/2û
✓T(low, high)的根结点是mid
✓根结点的左子树是Rlow,…,Rmid-1对应的二叉判定树
✓根结点的右子树是Rmid1,…,Rhigh对应的二叉判定树。
对半查找算法的每次成功查找正好对应判定树的一个内结点元素比较次数为该结点的深度加1即从根到该结点所经过的结点数。
每次不成功的查找对应判定树的一个外结点元素比较次数恰好为该结点深度即根到该节点所经过的内结点数
平均失败的查找长度外节点深度之和/外节点数3.5
平均成功查找长度内节点深度之和)/内节点数1 下面的是2.9 ➢优点平均查找效率不超过O(logn) 比顺序查找高。
➢缺点
✓适用于有序数组对有序链表难以进行二分查找。
✓适用于静态查找场景若元素动态变化频繁增删后
为了维持数组有序需要O(n)时间调整与顺序查找相比
就没有优势了。 3,斐波那契查找
斐波那契数列f00,f11;fifi-1fi-2 斐波那契查找 如果一个数组的长度是一个斐波那契数-1 ,那么他的左右就被分为了左边F(k-1)-1中间一个右边F(k-1)-
所以我们可以尝试根据斐波那契数列来优化查找 假定数组中元素个数n是某个斐波那契数减1即nFk-1。
令mid ¬ Fk-1把K与R[mid]比较若
➢K R[mid]在R[1]…R[Fk-1-1]内继续查找
➢K R[mid]在R[Fk-11]…R[Fk-1]内继续查找
➢K R[mid]则查找成功。 int FibSearch(int R[], int n, int K, int F[], int k){
int low1,highn;
while(low high){
int midlowF[k-1]-1; //因为我们的F[k]f[k-1]f[k-2],现在以f[k-1]为mid
if(KR[mid]) {highmid-1; k--;}//我们抛弃了f[k-2] ,查找范围从low--lowf[k]---low---lowf[k-1]
//长度为 f[k-1]-1
else if(KR[mid]) {lowmid1; k-2;} //我们抛弃了f[k-1],从low--f[k]---lowf[k-1]--lowf[k]
//长度为f[k-2]-1
else return mid;
}
return -1;
} 本质是从黄金比例查找
并且进入左边的几率更大,所需要的比较次数少, 4,插值查找
根据数学所学,根据直线算出可能的横坐标,假设原来的都是均分布且线性增长 平均时间复杂度:loglogn ---n
从O(logn)到O(loglogn)优势并不明显除非查找表极长
或比较操作成本极高。
比如n232 » 42.9亿
logn log232 32
loglogn log32 5
➢需引入乘除法运算。
➢元素分布不均匀时效率受影响。
➢实际中可行的方法首先通过插值查找迅速将查找范围缩
小到一定的范围然后再进行对半查找或顺序查找。 5,分块查找:
将大数组分成若干子数组块每个块中的数值都比后一块中数值小块内不要求有序建一个索引表记录每个子表的起始地址和各块中的最大关键字 查找的过程:先块间对半查找,再内部顺序查找,类似组相联cache
