2011年12月14日 星期三

PKU2081-Recaman's Sequence

如果直接按照定義來建表的話,每次檢查是否和前面重複需要O(n)
作n個這樣的數列就得O(n^2),會超時
既然只是簡單的檢查重複、只要支援插入,
那麼hash每次O(1)顯然是很好的選擇 (discuss有人給出了這題最大的答案...)

不過類似的功能用std::map來實作O(nlgn)也是能達到通過的標準

(其實這應該有數學規律可找...)

1 則留言:

jung 提到...

您好:
冒昧打擾,我是位高中教師,最近指導學生研究Recaman's Sequence ,在搜尋時連結到您的網站,不知您對此數列是否覺得有什麼規律的感覺,目前學生的研究有些停頓了。
PS:我們也寫了簡易的程式,單純讓電腦去跑每一項的值,正如你所說,需要愈多項所需的時間就多得更可怕。

張貼留言