假设我有以下算法:
procedure(n)
if n == 1 then break
R = generaterandom()
procedure(n/2)
现在我明白了这个算法的复杂度是 log(n)
但它是 log(n)
调用随机生成器还是 log( n)-1
因为当 n==1
时它不会被调用。
很抱歉,如果这很明显,但我一直在四处寻找,并没有在任何地方真正说明确切的答案是什么。
最佳答案
生成器有ceil(log(n))次调用
使用归纳法证明:
假设:
有ceil(log(k))
为每个 k<n
调用生成器
基地:
log_2(1) = 0 => 0 次调用
步骤:
任意n>1
有一个电话,然后从假设ceil(log(n/2)
递归调用中的更多调用。
这给了我们一共ceil(log(n/2))+1 = ceil(log(n/2)) + log(2) = ceil(log(n/2 * 2)) = ceil(log(n))
通话
QED
注意:此处所有日志均以2为底。
关于algorithm - 调用了多少次生成器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15019945/