作者:z苏苏575 | 来源:互联网 | 2022-12-10 02:54
在页146中Algorithms Fourth Edition
,给出了快速联合算法的最差时间复杂度的证明.它说
假设具有i个节点的树的高度具有log(i)的最大高度.
给定i + j = k,i <= j,当i和j节点的树被联合时,树的高度= 1 + log(i)= log(i + i)<= log(i + j) = log(k).
我不明白为什么1 + log(i) = log(i + i)
.
1> OmG..:
因为log(i + i) = log(2i) = log(2) + log(i)
并且log(2) = 1
,我们可以说log(i + i) = 1 + log(i)
.