algorithm - 复发的复杂性

Question

给定，

L(n) = 0 其中 n = 1， L(n) = L(n/2) 其中 n > 1a) 求 L(25)。b) L 的复杂度是多少。

请回答以上两个问题并说明你的答案

Answer 1

它将是O(logn)

当 n 除以 2 时。它在停止前运行了大约 logn 步。

n->n/2->n/4->n/8..n/2^k...1

so k=log(n)

It will be O(k)~O(logn).

它没有为奇数定义。

但是如果我们将 floor 考虑为一个数字，那么它就像

L(25)=L(12)=L(6)=L(3)=L(1)=0... 

我建议你先知道这个问题。