包含兩次遞歸調用算法的預期運行時間

Function(A, n) 
/* A is an array of integers 
/* random is a function that returns an integer between 1 and (in this case) n-1 

    if(n<=1) then return (A[1]) 
    else 
     x←0； 
     for i←1 to n-1 do 
     A[i]←A[i]-A[i+1] 
     x←x+A[i] 
     end 
     k←Random(n-1) 
     x←x+Function(A,k) 
     x←x+Function(A,n-k) 
     return(x) 
    end

我不明白爲什麼這種算法的最壞情況是當k = 1或n-1時，最好的情況是當k = n/2時。如何確保2ET（n/2）的預期運行時間小於ET（n-1）？包含兩次遞歸調用算法的預期運行時間

來源

2017-05-28 vinda lee

提示：做一些代數摸出（說）了多少次'X←X + A [1]'爲執行在您確定的3個案例中給定N個。（通過使N爲2的冪來簡化代數） –

[this]的可能重複（https://stackoverflow.com/questions/44223411/expected-running-time-of-the-algorithm-containing-two遞歸調用）遞歸問題 –

這是一個老玩笑。這很有趣*第一次*時間.... –

您的代碼具有與QuickSort相同的遞歸結構。因此，與QuickSort一樣，最壞的情況（k始終爲1，或者k始終爲n-1）爲O（n^2），平均情況爲O（n log n）。

在最壞的情況下的代碼的遞推關係是

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

（它解決了到T（n）= O（N^2），使用可伸縮的）

用於預期的遞推關係代碼的運行時間是：

T(n) = n + sum(k=1..n-1)[T(k) + T(n-k)]/(n-1)

注意有一個總和，它計算基於隨機值k的平均運行時間。

這是有點棘手來解決，但可以在這裏找到分析：https://en.wikipedia.org/wiki/Quicksort#Using_recurrences

來源

2017-05-28 05:22:57

包含兩次遞歸調用算法的預期運行時間

回答

相關問題