杭州做网站公司排名,模板之家下载,seo排名系统,福建平潭建设局网站各种查找算法的效率
顺序查找 一般顺序表#xff08;没有顺序#xff0c;随机排列#xff09; 成功时平均查找长度#xff1a; 1 . . . n n n 1 2 \frac{1...n}{n}\frac{n1}{2} n1...n2n1失败时平均查找长度#xff1a; n n n 有序顺序表#xff08;按照递增或递…各种查找算法的效率
顺序查找 一般顺序表没有顺序随机排列 成功时平均查找长度 1 . . . n n n 1 2 \frac{1...n}{n}\frac{n1}{2} n1...n2n1失败时平均查找长度 n n n 有序顺序表按照递增或递减排列 成功时平均查找长度 1 . . . n n n 1 2 \frac{1...n}{n}\frac{n1}{2} n1...n2n1失败时平均查找长度 1 2 . . . n n n 1 n 2 n n 1 \frac{12...nn}{n1}\frac{n}{2}\frac{n}{n1} n112...nn2nn1n 折半查找二分查找 用折半查找法找到给定值的比较次数不会超过树的高度n个元素的树高为 ⌈ l o g 2 ( n 1 ) ⌉ \lceil log_2(n1)\rceil ⌈log2(n1)⌉成功时的平均查找长度 A S L 1 n ( 1 × 1 2 × 2 3 × 4 . . . h × 2 h − 1 n 1 n l o g 2 ( n 1 ) − 1 ≈ l o g 2 ( n 1 ) − 1 ASL\frac{1}{n}(1\times 12\times 23\times 4...h\times 2^{h-1}\frac{n1}{n}log_2(n1)-1\approx log_2(n1)-1 ASLn1(1×12×23×4...h×2h−1nn1log2(n1)−1≈log2(n1)−1折半查找的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n) 分块查找索引顺序查找 平均查找长度 A S L L I L S ASLL_IL_S ASLLILS L I L_I LI为索引查找的平均查找长度 L S L_S LS为块内查找的平均查找长度 如将长度为n的查找表均匀地分成b块每块有s个记录在等概率情况下若在块内和索引表中均采用顺序查找则平均查找长度为 A S L L I L S b 1 2 s 1 2 s 2 2 s n 2 s ASLL_IL_S\frac{b1}{2}\frac{s1}{2}\frac{s^22sn}{2s} ASLLILS2b12s12ss22sn。可见若 s n s\sqrt{n} sn 则平均查找长度取最小值 n 1 \sqrt{n}1 n 1 树型查找 二叉排序树主要取决于树的高度 若二叉排序树的左右子树高度之差不超过1即平衡二叉树则平均查找长度为 O ( l o g 2 n ) O(log_2{n}) O(log2n)若二叉排序树是一个只有左右孩子的单支树则平均查找长度为 O ( n ) O(n) O(n) 平衡二叉树查找过程与二叉排序树相同 平均查找长度为 O ( l o g 2 n ) O(log_2n) O(log2n) 因为含有n个节点的平衡二叉树的最大深度为 O ( l o g 2 n ) O(log_2n) O(log2n) 红黑树 平均查找长度为 O ( l o g 2 n ) O(log_2n) O(log2n) B树和B树 散列表 虽然散列表在关键字与记录的存储位置之间建立了直接映像但由于冲突的产生使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此仍需以平均查找长度作为衡量散列表的查找效率的度量。 散列表的查找效率取决于三个因素散列函数、冲突处理的方法和装填因子。 直观的看 α \alpha α越大表示装填的记录越满发生冲突的可能性越大。
折半查找二分查找与二叉排序树的区别
二叉排序树与二分查找折半查找的查找过程相似平均时间性能差不多。不同点如下
唯一性二分查找的判定树唯一而二叉排序树随着关键字插入顺序不同可能生成不同的二叉排序树插入和删除二分查找的对象是有序顺序表若有插入和删除节点的操作所花的代价是 O ( n ) O(n) O(n)二叉排序树则无需移动节点只需修改指针即可完成插入和删除操作适用于动态还是静态当有序表是静态查找表时宜用顺序表作为其存储结构采用二分查找实现找操作若有序表是动态查找表应选择二叉排序树作为其逻辑结构
平衡二叉树和红黑树的区别
二者的查、插、删的时间复杂度都是 O ( l o g 2 n ) O(log_2n) O(log2n)区别如下
平衡二叉树的插入和删除很容易破坏平衡特性故插/删后大都需要调整树的形态计算平衡因子找到最小不平衡树LL/RR/LR/RL这样一来时间开销就很大而红黑树由于其特性很多时候插入删除后并不会破坏红黑特性即便需要调整一般也都可以在常数级时间内完成即虽然二者的插、删、查的时间复杂度都是 O ( l o g 2 n ) O(log_2n) O(log2n)但实际上红黑树的插入和删除性能更好一点平衡二叉树的查找性能更好一点使用场景平衡二叉树适用于以查为主、很少插入/删除的场景红黑树适用于频繁插入、删除的场景实用性更强
B树和B树的区别
二者相同点是除根节点外最少 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m⌉个分叉确保节点不要太空。任何一个节点的子树都要一样高确保绝对平衡
-m阶B树m阶B树类比二叉查找树的进化 -- m叉查找树分块查找的进化 -- 多级分块查找关键字与分叉n个关键字对应n1个分叉子树n个关键字对应n个分叉节点包含的信息所有节点中都包含记录的信息只有最下层叶子节点才包含记录的信息每个节点能存的信息更多因此可以使树更矮且叶节点包含所有的关键字查找方式不支持顺序查找。查找成功时可能停在任何一层节点查找速度不稳定支持顺序查找。查找成功或失败都会到达最下一层节点查找速度稳定
