複雜性復發

Question

鑑於，

L（N）= 0，其中n = 1， L（N）= L（N/2），其中n> 1 a）求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). 

它沒有爲奇數定義。

但是，如果我們考慮到地板的一些，然後它會像

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

我會建議你先知道的問題。