以下遞歸代碼的時間複雜度（以大O表示法）？

Question

以下遞歸代碼的Big-O時間複雜度（O）是什麼？

public static int abc(int n) { 
    if (n <= 2) { 
     return n; 
    } 
    int sum = 0; 
    for (int j = 1; j < n; j *= 2) { 
     sum += j; 
    } 
    for (int k = n; k > 1; k /= 2) { 
     sum += k; 
    } 
    return abc(n - 1) + sum; 
} 

我的回答是O(n log(n))。這是對的嗎？

Answer 1

我在哪裏坐......我認爲運行時間是O（n日誌n）。這是爲什麼。

• 您正在ň調用該函數。功能絕對取決於ñ以下兩個操作均採用次數：

  • 你環路高達2 *日誌（n）的值遞增的總和。

對於最壞的情況下，ñ非常大，但整體運行不會改變。最好的情況是n < = 2，這樣只有一個操作完成（循環不會發生）。