計算預期時間遞歸程序的複雜性

Question

我希望確定的遞歸算法的平均處理時間T（N）：

int myTest(int n) { 
    if (n <= 0) { 
    return 0; 
    } 
    else { 
    int i = random(n - 1); 
    return myTest(i) + myTest(n - 1 - i); 
    } 
} 

提供，該算法隨機（INT n）的花費一個時間單元返回 一個在[0，n]範圍內均勻分佈的隨機整數值，而其他指令的花費時間可以忽略不計（例如，T（0）= 0）。

這當然不是簡單的形式T（n）= a * T（n/b）+ c，所以我迷失在如何寫它。我不知道如何編寫它，因爲我每次都從0到n-1範圍內隨機選擇一個數字，並將它提供給函數兩次，並要求這兩個調用的總和。

Answer 1

遞推關係是：

T(0) = 0 
T(n) = 1 + sum(T(i) + T(n-1-i) for i = 0..n-1)/n 

第二可以簡化爲：

T(n) = 1 + 2*sum(T(i) for i = 0..n-1)/n 

乘以N：

n T(n) = n + 2*sum(T(i) for i = 0..n-1) 

注意到(n-1) T(n-1) = n-1 + 2*sum(T(i) for i = 0..n-2)，我們得到：

n T(n) = (n-1) T(n-1) + 1 + 2T(n-1) 
     = (n+1) T(n-1) + 1 

或者：

T(n) = ((n+1)T(n-1) + 1)/n 

這樣做的解決方案T（N）= N，您可以通過伸縮系列獲得，或者通過猜測的解決方案，然後將其代來證明它的作品。