計數排序 - 我知道它是如何工作的，但無法解決它

如果滿足某些條件，則計數排序可按線性時間排序。構建一個序列A = < a1; ：：：; a10> n = 10個數字，其中計數排序需要theta（n^7）時間。解釋你的選擇。計數排序 - 我知道它是如何工作的，但無法解決它

我的方法;

如果我選擇A = [0,0,0,1,2,3,4,5,6,2]，其中n = 10 C new將是[3,4,6,7,8 ，9,10]和B = [0,0,0,1,2,2,3,4,5,6] 這是如何計算排序工作（根據講座），但我如何證明它有運行時間n次方7？通過根據僞碼計算每個步驟的運行時間，然後添加？

來源

2017-02-18 Muhammad Yousaf

看起來像一個問題給你張貼在這裏。 – nullpointer

是的，因爲我知道如何計數排序工作，我試着使用如下; 如果我選擇A = [0,0,0,1,2,3,4,5,6,2]，其中n = 10 C new將是[3,4,6,7,8,9， 10]和B = [0,0,0,1,2,2,3,4,5,6] 這是如何計算排序工作（根據講座），但我如何證明它已運行n次冪7？通過根據僞碼計算每個步驟的運行時間，然後添加？ –

這個問題似乎是不可能解決的，因爲Theta符號在極限中將運行時限作爲n的函數進行討論，所以在運行時爲Theta（n^7）的情況下，應該有固定n和固定序列。對於任何固定的大小和順序，運行時間爲O（1）。 – templatetypedef

選擇A []，使得範圍是n^7，在這種情況下是10^7。它可能是A [] = {0,0,0,0,0,0,0,0,0,9999999} ;.由於計數陣列大小爲10^7，因此對陣列進行單次掃描以產生輸出將需要10^7個循環。

來源

2017-02-18 18:49:46 rcgldr

Waow ..有道理,,,一個完美的答案。萬分感謝！！！我也和我的教授討論過，他也說過一樣。再次感謝你！ –

計數排序 - 我知道它是如何工作的，但無法解決它

回答

相關問題