愚蠢選擇程序？

Question

我最近在分析第k個最小元素算法後寫了一個程序，首先沒有重複的情況。

但是，現在我想分析預期的漸近運行時間，用於查找某個數組的中位數，例如當存在完全相同的j重複數時。我還沒有修改過我的代碼，因此，由於j重複，性能變慢了一點。

我不知道如何開始？任何人都可以指向我這樣的復發關係嗎？

我得出以下，其中n是輸入數組

T(n) <= 1/2*T(3/4*n) + 1/2*T(n) 

的大小，但我還不是很清楚如何與涉及重複鍵繼續。

感謝

Answer 1

隨機化的解決方案as demonstrated here是

T(n) <= T(3/4*n) + n-1 => T(n) <= 4n 

該算法的複雜性可能取決於j但不要指望它是奇蹟般地比線性時間要少。爲什麼？取一個大小爲n/2的隨機數組，完全複製它，然後針對具有重複的問題運行理想的算法。你必須

T(n) <= 4(n/2) => T(n) <= 2n 

當每個元素被重複兩次（正好n/2重複）