if if遞歸最壞時間複雜度

我有一些麻煩弄清楚下面代碼的最壞時間複雜度。
（這不是一門功課，看https://leetcode.com/problems/integer-replacement/description/。）if if遞歸最壞時間複雜度

int recursion (int n) { 
    if (n == 1) 
     return 0; 
    if (n % 2 == 0) { 
     return recursion(n/2) + 1 
    } else { 
     return min(recursion(n/2 + 1) + 1, recursion(n - 1)) + 1; 
    } 
}

我唯一知道的是，當N == 2^k(k > 0)，最壞的時間複雜度爲O(logN)。但是，我不清楚何時N不是2^k。因爲即使number/2仍然可以得到奇數。有人說它仍然是O(LogN)，但我不相信。

我知道代碼不是最好的解決方案，只是想分析時間複雜性。我試過遞歸樹和聚合分析，似乎沒有幫助。

來源

2017-11-11 nathan

你的其他情況有錯誤的說法，它應該是'（n + 1）/ 2' –

@BlackMamba。嗨，（n + 1）會溢出。但我有其他錯誤。 Updated.Thanks非常多 – nathan

我看到了leetcode問題陳述。我不知道在前兩個版本中，最後一個分支（用'min'選擇其中一個）與它有關 - 它不應該是「an'else」的一部分，如果「then」無論如何，''終止於無條件的'return'。 – greybeard

如果n是偶數，我們知道T(n) = T(n/2) + 1，如果n是奇數我們知道 T(n) = T(n/2 + 1) + T(n-1) + 1。在後一種情況下，由於n很奇怪，我們知道n-1必須是偶數。如果n/2 + 1甚至是T(n) = T(n/4) + T(n/2) + 3並且如果n/2 + 1是奇數T(n) = 2*T(n/4) + T(n/2) + 3。

從上面的討論，在最壞的情況下T(n)是基於在一般情況下，T(n/2)和T(n/4)定義。從Akra-Bazzi Theorem我們可以說，T(n) = O(n^((log(1+sqrt(5))-log(2))/log(2))) ~ O(n^0.69)（來自第一種情況）和T(n) = O(n)來自第二種情況（其中n/2 + 1是奇數）。

但是，對於更復雜的情況，我們應該在我們的分析中仔細檢查。

來源

2017-11-11 18:44:30 OmG

嗨，阿克拉 - 巴齊引起了我的思想。我將這個應用於T（n）= T（n/4）+ T（n/2）。 – nathan

如果'n'是奇數，那麼'n/2 + 1'可以是奇數或偶數 - 考慮n = 7和n = 9。 – algrid

@OmG，如果'n = 9'，則'n/2 + 1'等於'5'。 – algrid

if if遞歸最壞時間複雜度

回答

相關問題