algorithm - 调用了多少次生成器？

Question

假设我有以下算法:

procedure(n)
   if n == 1 then break
   R = generaterandom()
   procedure(n/2)

现在我明白了这个算法的复杂度是 log(n) 但它是 log(n) 调用随机生成器还是 log( n)-1 因为当 n==1 时它不会被调用。

很抱歉，如果这很明显，但我一直在四处寻找，并没有在任何地方真正说明确切的答案是什么。

Answer 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为底。