d-Ary 堆的运行时间如何从 O(log d n) 简化为 O( (log n) / (log d))？
正确的简化是：log d n = log d * log n
除法简化是如何得出的？
问问题
531 次
2 回答
4
这使用公共恒等式在对数底之间进行转换：
logx(z) = logm(z) / logm(x)两边都乘以 log m (x)，得到：
logm(z) = logx(z) * logm(x)这相当于您网站问题中的答案。
更多信息可在此处获得。
于 2012-06-23T02:27:47.820 回答
3
认为
x = log d (n)等效地，我们有，
n = d x然后
日志2 n = 日志2 (d x ) = x 日志2 (d)除以 log 2 (d) 得到：
日志2 (n) / 日志2 (d) = x所以
log 2 (n) / log 2 (d) = x = log d (n)
当然，假设d是固定的，那么 log 2 (d) 只是一个常数。所以
O（log d（n））= O（1 / log 2（d）* log 2（n））= O（log 2（n））也就是说，就 Big-Oh 表示法而言，您可以将任何对数底（大于 1）更改为任何其他（此类）对数底。所以习惯上只是去掉基数并写 O( log(n) )
于 2012-06-23T02:22:27.940 回答