→ YuxiWen: 搜尋是個好東西 01/27 00:22
→ joeboy: 我有找過了QQ 01/27 00:54
推 w181496: 7b.應該是i*(i-1)/2+j-1 01/27 06:21
→ w181496: 第8應該是8 5 5 01/27 06:22
→ w181496: 15題theta(n)吧 01/27 06:25
→ yupog2003: 10用以n為底的radix sort，把數字都轉成n進制 01/27 08:04
→ joeboy: 這樣時間會不會變成kn？ 01/27 13:12
→ yupog2003: 範圍是1~n^2，以n為底的話最多3位數，O(3n)=O(n) 01/27 13:19
→ yupog2003: 甚至3位數的數字也只有n^2一個數而已，優化一下還可以 01/27 13:20
→ yupog2003: 變O(2n) 01/27 13:20
推 DZASHIANG: 10用n^1/2當basis 用radix sort 包含4次counting sort 01/27 13:35
→ DZASHIANG: ,4*O( n(input)+n^1/2(basis的值域）=O(S) 01/27 13:35
推 yupog2003: 我發現我想錯了，應該D大才是對的 01/27 13:42
→ YuxiWen: 我寫要做5次耶，比如n取100, 取10為base, 範圍為1~10000 01/27 13:49
→ YuxiWen: ，不過10000有5個bit說 01/27 13:49
→ yupog2003: 用n^1/2當base做radix sort不知道可不可以？ 01/27 13:52
→ yupog2003: 5個bit，數列長度為n^1/2，基底為n^1/2，time complexi 01/27 13:53
→ yupog2003: =O(5*(n^1/2+n^1/2))=O(10*n^1/2)=O(n^1/2)=O(|S|) 01/27 13:54
→ yupog2003: 剛剛忘記考慮base為n的話會比|S|大 01/27 13:56
→ yupog2003: 應該是5個bit沒錯，不過5個bit只有一個數，可以優化 01/27 13:56
推 YuxiWen: 對耶，寫太快，忘了可以直接先挑出來 01/27 14:03
→ yupog2003: 但應該也是可以拉，反正都常數 01/27 14:07
→ DZASHIANG: 如果1-10000，每個數應該也可以用4個digit 表示，對應 01/27 14:11
→ DZASHIANG: 到0-9999 有誤請指正... 01/27 14:11
推 yupog2003: 我覺得這也是一種優化方法 01/27 14:12