我學習了一個測試，這個星期我已經和我對面，詢問審查問題就來了......基數排序時間
二十萬元範圍爲0的正整數。 。 。 99,999,999按LSD基數排序。比較使用基數0的性能。 。 。 9999和基數0。 。 。 9.顯示你的 工作。我知道基數排序的時間是theta（d（k + n））;其中d =數字位數k =基數大小，n =記錄數。
我明白十進制基數是theta（8（10 + 20,000,000）），對嗎？
千位基數是多少？ THETA（3（1000 + 20000000））？
你說得對，運行時間是O（d（n + k））。這可能有助於明確d和k之間的關係。如果您處理的數字從0到數字U，則每個數字中的基數k數字將爲Θ（日誌 k U）= Θ（log U/log k）。這意味着運行時更適合O（log U（n + k）/ log k）。
在你的情況下，k與n相比非常小，所以這個運行時會有O（n log U/log k）。
您聲稱運行時間爲Θ（8（10 + 20,000,000））和Θ（3（1,000 + 20,000,000））有點奇怪。請記住Θ表示法談論長期增長率而不是個別價值，所以用這種方式插入價值沒有意義。但是，你的基本論點是正確的。從基數10到基數10000是基數的數量級的3倍增加，所以你應該期望算法在基數較大的情況下快三倍。
也就是說，還有很多其他因素可能會在實踐中搞砸這個時機。引用的局部性在執行大量數組操作的算法的運行時間中起着巨大的作用，並且隨着您增加桶的數量，您的局部性會逐漸變差。這可能實際上最終使大基排序比小基排序慢，因爲即使輪數較少，由於緩存效應每輪都會花費更長的時間。沒有嘗試過，我敢打賭，這很有可能是在實踐中會發生的。
計算你的數字，它不是千位基數。 –
那麼它應該是theta（2（10000 + 20,000,000））？那個基數會被稱爲什麼？ – user1013032
Myrias，如果你想吹噓一點希臘。如果你想要被理解的話，還是一萬個。 –