劃分和征服算法數值

如果使用隨機快速排序算法對大小爲n = 1000的文件進行排序需要10 ms，那麼大約需要多長時間對大小爲n = 1000000000的文件進行排序（假設所有數據在主存儲器中可用）劃分和征服算法數值

2015-07-19 Shiv KuMar

這可能屬於math.stackexchange，因爲它是一個數值計算問題，不以任何方式，除了表面上的任何方式。他們應該知道，快速排序的預計運行時間是Theta（n log n），如果不是那麼只是告訴他們，他們應該沒有問題幫助你。 – user2566092

你使用臺式電腦嗎？快速排序中的一個操作需要大約1微秒的時間，這太慢了。也許你的實現/時間測量有問題，或者排序需要二次時間。 – stgatilov

如果隨機Quicksort的平均時間（或基本操作的數量）是O（n log（n））並且對於n = 10^3需要10ms，則意味着關係10 = t 10^3 log（10^3），其中t是操作持有的時間。根據以前的關係，您可以通過一次基本操作t = 10 /（10^3 log（10^3））ms獲得計算機花費的時間。因此，以n = 10^9結束的時間爲t 10^9 log（10^9）。用t = 10 /（10^3log（10^3））代替，您的計算機需要10 /（10^3log（10^3））10^9log（10^9）ms或10^7 9/3 ms。

是你在找什麼？

來源

2015-07-19 20:34:52 marc1s

劃分和征服算法數值

回答

相關問題