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))电话总数

量子点

注意：这里所有的日志都是以 2 为底的。

Answer 2

根据大师定理，您的方法可以写为 T(n) = T(n/2) + O(1)，因为您将 n 分成每个函数调用的一半，而这正是 O(log n)。- 我意识到你不是在要求复杂性分析，但就像我提到的，这个想法是一样的（即找到调用的数量等于它的复杂性）