1
我最近在分析第k個最小元素算法後寫了一個程序,首先沒有重複的情況。愚蠢選擇程序?
但是,現在我想分析預期的漸近運行時間,用於查找某個數組的中位數,例如當存在完全相同的j
重複數時。我還沒有修改過我的代碼,因此,由於j
重複,性能變慢了一點。
我不知道如何開始?任何人都可以指向我這樣的復發關係嗎?
我得出以下,其中n是輸入數組
T(n) <= 1/2*T(3/4*n) + 1/2*T(n)
的大小,但我還不是很清楚如何與涉及重複鍵繼續。
感謝
我們幫不了你,除非我們有你所談論的功能。 – 2012-04-23 06:47:25