算法:考察二分算法的平均成功查找长度1.5logn是如何计算出来的,请看图 10C

图片说明图片说明图片说明我想知道谁看懂了那个递推分析的过程,尤其是那个递推式。。。能给我讲解一下吗

3个回答

每次迭代有三种可能;查找失败则返回-1,这个版本的代码很直观,但是也有一些缺陷:
每次迭代的判断次数不平衡,有可能只需判断一次,也有可能要判断两次;
有多个元素命中时,不能保证返回秩最大(或者最小)者;
查找失败时,不能指示失败的位置;
针对第一个问题,我们这里要提出一个概念,叫作查找长度;
我们在进行二分查找的迭代过程所涉及的计算,无非两类:元素比较大小和秩的算数运算及赋值。元素的秩是整数,它的操作属于O(1)复杂度的基本操作,而元素比较大小一般来讲也是O(1)复杂度的基本操作,但是我们说当向量的元素类型很复杂时,其比较操作未必能保证在常数时间内完成!因此就时间复杂度的常系数而言,元素比较操作的权重远远高于秩的运算和赋值,而查找算法的整体效率也更主要地取决于元素比较操作的次数,即所谓的查找长度。
接下来我们以长度为7的向量为例,分析其成功查找长度和失败查找长度:(涉及的具体证明可以查阅原书)

每一个成功查找所对应的查找长度,仅取决于向量的长度n以及目标元素所对应的秩,而与元素的具体数值无关,因此我们可以得出,n = 7时,各元素所对应的成功查找长度和失败查找长度分别为:

{4, 3, 5, 2, 5, 4, 6} 平均为4.14;

{3, 4, 4, 5, 4, 5, 5, 6} 平均为4.50;

我们可以看出,迭代次数相同的情况下对应的查找长度不尽相同!这就是所谓的不平衡,那么对于更加一般的情况(n = 2^k - 1),我们采用递推分析法:

递推式:C(k) = [C(k-1) + (2^(k-1) - 1)] + 2 + [C(k-1) + 2 * (2^(k-1) - 1)]

C(k)是查找长度;

[C(k-1) + (2^(k-1) - 1)] 代表经过一次成功的比较,查找范围深入到左侧部分;

2 代表经过两次失败的比较,命中要查找的元素;

[C(k-1) + 2 * (2^(k-1) - 1)] 代表经过一次失败的比较和一次成功的比较,查找范围深入到右侧部分;

最终我们可以得出平均查找长度为O(1.5logn);对于失败查找长度同样可以得出为O(1.5logn);

你说的是C(k)那个递归式吗?如果是的话请看下面的一张图片
图片说明
我们将(a)那一层想象成第k层,下面的(b)看作是k-1层。我们把第k层删掉,那么第k-1层就变成了顶层。
k-1层有两个分支,一左一右。你应该不难看出,顶层的查找长度(也就是一次查找成功的查找长度)必然是2。
那么对于左面的k-1层来说它的顶层是3,右面的顶层是4。稍加观察你会发现左面的k-1层的所有元素的查找长度都会相对于以k-1层为顶层时的查找长度多1。同样右面的k-1层的所有元素查找长度会相对于以k-1层为顶层时的查找长度多2。所以C(k)中需要把这些长度补上,然后在加上第k层的查找长度2即为C(k).

首先,每个元素要么查1次继续迭代,要么查2次继续迭代,要么查两次结束。
此时,总次数为
[2^(k-1)-1]*1+[2^(k-1)-1]*2+2
之后,继续迭代查找长度要加上2*C(k-1)
所以总次数
C(K)=c(K-1)+[2^(k-1)-1]+c(K-1)+[2^(k-1)-1]*2+2

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问