找到CN和時間複雜度

Question

通過我的復發，我試圖解決這個復發研究 你可以查一下

public static int java(int N) { 
    if (N == 1) 
    return 1; 
    return (java(N/2) + java(N/2)); 
} 

我覺得這是方程

C(1) = 1 
CN = 2CN/2 + 1 

和複雜度爲O（log N）

你能幫我查一下嗎

Answer 1

public static int java(int N) { 
    if (N == 1) 
    return 1; 
    return 2 * java(N/2); 
} 

而不是調用兩次相同的，只是乘以2就沒有需要重新計算它對於相同的輸入。

複雜性是O(log N)，因爲您每次都將問題分解爲因子2。