Posted on 2009-11-30 11:17
王之昊 閱讀(225)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
數(shù)學(xué)
約瑟夫的兩個(gè)經(jīng)典問(wèn)題：
- 最后活下來(lái)的人是誰(shuí)？
- 殺人序列如何？
對(duì)于問(wèn)題一，有遞推式可以做到O(n)， 具體數(shù)學(xué)上也提供了一種基于上下界知識(shí)的O(logn)的算法。不過(guò)對(duì)數(shù)的底比較小。
對(duì)于問(wèn)題二，比較常見(jiàn)的方法是O(n^2)，用樹(shù)狀數(shù)組+二分的思想可以做到O(n*logn*logn)