我想使用重復替換方法找到這個函式的時間復雜度。我知道它是這樣的
T(n) = 2T(n/2) Θ(1) =2^2T(n/2^2) 2Θ(1) Θ(1) 。. . =nΘ(1) (2^k-1)Θ(1)
結果是 O(n)。我只是不明白為什么最終結果是 O(n)。它從哪里來的？
void foo(int n){
if(n>1){
foo(n/2);
foo(n/2);
}
}
uj5u.com熱心網友回復：
想象數字 ?? 用 ?? 彈珠線表示：
????????????????
第一個遞回呼叫將處理其中的一半，而另一個遞回呼叫將處理另一半：
????????|????????
這些遞回呼叫中的每一個都將執行相同的操作：
????|????|????|????
所以它一直持續到基本情況：
?|?|?|?|?|?|?|?|?|?|?|?|?|?|?|?
有時彈珠的數量會是奇數，然后我們可以想象中間的彈珠會被排除在遞回呼叫之外。
所以基本情況最多會執行 ?? 次：每個彈珠執行一次。這是 O(??)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510108.html
標籤：算法排序时间复杂度