我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿主页 > 调度模块 >

C语言 二分法查找次数公式怎么推导?

归档日期:07-21       文本归类:调度模块      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  对具有n个元素的有序数组进行二分法查找,要分析的比较次数,可以使用画二叉判定树的方法来分析。该二叉判定树的高度为[log2(n)]+1层,此即为二分查找的最多比较次数,比如:n=1000,则最多比较[log2(1000)]+1=9+1=10次。

  如果要计算平均的比较次数,则需要对二叉判定树中的每个节点进行分析,处于第一层的比较1次,第二层的比较2次,第三层比较3次,依次类推……把各个节点的比较次数累加,再处于节点数(元素个数)即为平均比较次数,这里假设查找是在等概率的情况下进行的。

  举个例子:有9个元素的有序数组,对每个元素按1,2,3...8,9进行编号,则其二叉判定树如下:

  图中可以看出,如果要找的元素处在第5个位置,则只要1次比较即可找到,若找第9个元素,则需要4次比较,算法分别比较了第5,7,8,9等4个元素。所以,平均的比较次数大概如下:

  等概率情况下,查找成功的平均比较次数为:(1*1+2*2+3*4+4*8+5*16+6*32+7*47)110=650110≈5.91次。

  展开全部令在a[i]~a[j] (j-i=n-1) 这n个有序的元素中查找元素x的查找次数为f(n),则:

  最多查找次数为f1(n)=┏Log2(n+1)┓ (向上取整)更多追问追答追问能不能用笔写一写,然后照一张相,发给我,谢谢你~~……追答分析:

  在3个元素中找,首先与中间一个,即a[2]比,若不是,则排除一半,在剩余的1个中找,最坏可能要找2次(1+1=2次);

  在4个元素中找,首先与a[2]比,若不是,则排除一半,最坏的可能在剩余的2个中找,除已比的一次外,最坏可能还要找2次(见第3行);于是最多是找1+2=3次

  至于直接计算的公式,就需要比较扎实的高中数学基础。追问两个元素的时候最坏找一次吧,第一次比较不是需要的元素,那么剩下的元素就是需要的元素。追答也有可能那不是要找的数据啊.

本文链接:http://i-zyczenia.net/diaodumokuai/1004.html