Question

数据结构，第二张图中画波浪线的那个式子是怎么推导的呢？





Answer 1

第一张图：

如图画红线地方，注意是等概率假设：

一共n节点，等概率找到节点j的概率pⱼ=1/n，找到节点j的查找长度cⱼ为节点j所在树的层数。则平均查找长度为p₀c₀+p₁c₁+…+pₙcₙ

当所查节点j处于第i层时，该层节点数为2^(i-1)，每个节点的查找概率都为1/n，每个节点的查找长度为对应的层数i，则该层所有节点的平均查找长度为i/n·2^(i-1)=1/n·2^(i-1)·i

一共h层节点，则p₀c₀+p₁c₁+…+pₙcₙ=1/n·2^(1-1)·1+1/n·2^(2-1)·2+...+1/n·2^(h-1)·h

=sum{i=1→h}1/n·2^(i-1)·i=1/n·sum{i=1→h}2^(i-1)·i

第二张图：

因为是折半查找，对n个节点的树先进行一次查找后，目标节点要么在一半的n/2个节点中，要么在另一半的n/2个节点中，也就是n个节点的查找次数等于n/2个节点的查找次数+1，也即C(n)=C(n/2)+1。

那么对于C(n/2)，继续递推，等于C(n/2/2)+1=C(n/2²)+1

即C(n)=C(n/2)+1=C(n/2²)+1+1=C(1)+1+1+...+1=O(log₂n)

进一步解释上面的结果：

若n恰好为2的k次幂，即n=2ᵏ，则k=log₂n

C(n)=C(2ᵏ)=C(2ᵏ⁻¹)+1=C(2ᵏ⁻²)+2=...=C(2⁰)+k=1+k=1+log₂n=O(log₂n)

若n不为2的k次幂，即2ᵏ⁻¹<n<2ᵏ，则k-1<log₂n<k，log₂n<k<log₂n+1

那么C(n)<C(2ᵏ)=1+k<log₂n+2，C(n)>C(2ᵏ⁻¹)=k>log₂n

所以log₂n<C(n)<log₂n+2，C(n)的计算复杂度仍为O(log₂n)

对于这个知识点，只要记住折半搜索的计算复杂度为O(log₂n)就可以了

追问

C(1)+1+1+...+1=log₂n这个式子是怎么来的呢？