如何找到下面代碼的時間複雜度？

你能解釋一下如何找到下面代碼的時間複雜度嗎？任何幫助讚賞。如何找到下面代碼的時間複雜度？

int boo(n) { 
    if (n > 0) 
    { 
     return 1 + boo(n/2) + boo(n/2); 
    } 
    else 
    { 
     return 0; 
    } 
}

2016-11-29 Yazgan

這可以幫助你http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation –

@DanielCorzo謝謝丹尼爾，我已經看到了這一點。這裏的情況有點不同。 – Yazgan

有時候這是好事，把它寫下來。當你開始時，它總結1 + boo（n/2）+ boo（n/2），它在第二行。

並且每個是n/2也被運行

等等，等等

所以在最後的同時呼叫的數量被exponencially生長，repetions的數量僅爲logharitmic，其在最後移除對方，你得到了O（N）。 PS：對最後一行進行倒數就足夠了，整個樹總是隻有一次更多的節點（減1），這在複雜性理論中是可以忽略的（你不關心常量，它乘以2）

2016-11-29 16:37:14 libik

非常感謝很多朋友（： – Yazgan

這個確切的問題來考試LOL再次感謝@libik – Yazgan

@Yazgan - 哇，我希望我是正確的：D ... – libik

回答