[理工] 105中央資演 一題

作者: ponponjerry (ponpon)   2019-01-26 15:46:47
先上題目
https://i.imgur.com/LX0srqZ.jpg
爬過文看到以前對答案的結果是42,但我覺得很奇怪,因為他們的結論是用O(n+K)去算
,其中n=5,k=(51-15)+1
我的疑問&想法是:
1.因為每個數字的十位數都不一樣,所以直接取十位數當值域就好了(也就是先mod 10)
,這樣的話k=5,n=5
2.實際所需的空間應該不是用Big-O去算吧?在演算法中,需要count[1…k] , start[1
…k] 跟output[1…n] ,所以空間需求是k+k+n吧?
3.這個空間需求的單位應該要寫什麼呢?寫bytes感覺又怪怪的,還是寫units就好了
煩請各位回答,預祝各位考試順利!
作者: nchuAM37 (應數37)   2019-01-26 17:09:00
他題目規定要用counting了 為什麼可以mod 10
作者: bmpss92196 (bmpss92196)   2019-01-26 17:19:00
我也不懂為何不是k+k+n
作者: sooge (老衲)   2019-01-26 18:31:00
我也覺得空間是k+k+n 不知道能不能兩個都寫
作者: y2j60537 (skkkkuu)   2019-01-26 18:52:00
我記得如果COUNTING SORT是用結束位置做紀錄可以只用一個Count[k]和output[k]就做完排序count[1...k]統計完之後用同個count[1...k]把他更新成結束位置
作者: eggy1018 (羅密歐與豬過夜)   2019-01-27 01:21:00
這題大家會想要剪掉最小+1再跑嗎?可以少一點空間,不過好像沒什麼必要,不知道各位大大怎麼寫

Links booklink

Contact Us: admin [ a t ] ucptt.com