PTT數位生活區 / C_and_CPP (C/C++)

Re: 雙層排序問題

看板C_and_CPP (C/C++)作者 (眠月)時間16年前 (2009/06/24 23:25), 編輯推噓5(5推 0噓 18→)
留言23則, 4人參與, 最新討論串6/6 (看更多)
※ 引述《yauhh (喲)》之銘言： : 這小事,只要寫個普通的對應程式,把字母對應為順序號碼: : enum Letter { : None = -1, : B = 0, R, : O, Y, : G, L, : P, W : }; : enum Letter charToLetter(char ch) { : switch (ch) { : default: : return None; : } : } : 雖然寫得很長,但就是 O(1) 程度,並且可以把不連續資料調整為連續資料. : 然後在任何 sort 的 compare 函式會看到這樣的程式碼: 媽阿，太累了吧 XD char a[255] ; a['B'] = 0 ; a['R'] = 1 ; a['O'] = 2 ; a['Y'] = 3 ; a['G'] = 4 ; a['L'] = 5 ; a['P'] = 6 ; a['W'] = 7 ; 這樣 a[c] 就知道優先順序啦 而且你講的那個 O(1) 也要 compiler 夠聰明才有，不然還是 O(n) -- To iterate is human, to recurse, divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.109.130
推
06/25 01:50, , 1F
switch case ? 應該是還是 O(n)吧?
06/25 01:50, 1F
→
06/25 02:52, , 2F
沒差啦,反正是小事
06/25 02:52, 2F
→
06/25 02:54, , 3F
原po只是問怎麼寫,給個方向;但一堆人拼命給越快越好的作法,
06/25 02:54, 3F
→
06/25 02:55, , 4F
這一點我很不能理解. 先給一個適當的作法不就可以了嗎
06/25 02:55, 4F
→
06/25 03:12, , 5F
and why did you remark you algo is O(1) -_-||
06/25 03:12, 5F
→
06/25 03:12, , 6F
(which actually not...)
06/25 03:12, 6F
→
06/25 03:23, , 7F
not to mention the solution is complicated O_O
06/25 03:23, 7F
推
06/25 03:42, , 8F
寫死在code裡面的switch case就算有1000000項也是O(1)
06/25 03:42, 8F
→
06/26 00:30, , 9F
It depends on the case value and the compiler.
06/26 00:30, 9F
推
06/26 00:37, , 10F
no, 1000000 is a constant
06/26 00:37, 10F
推
06/26 00:39, , 11F
對於寫死的switch是O(1) 我比較有興趣 compiler有說明嗎?
06/26 00:39, 11F
→
06/26 00:39, , 12F
或是哪家的compiler有說明? 有人看過的可以share一下
06/26 00:39, 12F
推
06/26 02:20, , 13F
我想講的只是.. n是input size, switch的數量並不會因為
06/26 02:20, 13F
→
06/26 02:20, , 14F
input而改變, 所以就算裡面有100000個case也還是constant
06/26 02:20, 14F
→
06/26 02:20, , 15F
time
06/26 02:20, 15F
→
06/26 02:21, , 16F
這點yauhh講的並沒有錯
06/26 02:21, 16F
→
06/26 22:50, , 17F
這樣算的話，那我乾脆說所有的 input 都是有限多的..
06/26 22:50, 17F
→
06/26 22:51, , 18F
對任何一個問題，我都用 code generator 生出 switch 碼
06/26 22:51, 18F
→
06/26 22:51, , 19F
然後交給 compiler 直接 output 答案就好..
06/26 22:51, 19F
→
06/26 22:51, , 20F
這種論點無異跟白痴一樣嘛..
06/26 22:51, 20F
→
06/26 22:52, , 21F
人家現在講的就是 case 的數目跟決策的時間..
06/26 22:52, 21F
→
06/26 22:52, , 22F
好的 compiler 遇到好的 case 可以做出 O(1) 的跳轉沒錯
06/26 22:52, 22F
→
06/26 22:52, , 23F
但是 general case 就不是
06/26 22:52, 23F
‣ 更多 yoco315 的文章
文章代碼(AID): #1AGaLpXr (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：
排序： 最新先 | 最舊先 | 留言數
5
23
Re: 雙層排序問題
yoco315
16年前, 06/24
1
1
Re: 雙層排序問題
ledia
16年前, 06/24
3
6
Re: 雙層排序問題
yauhh
16年前, 06/23
2
27
雙層排序問題
aoaay
16年前, 06/22
在新視窗開啟完整討論串 (共6篇)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yoco315 的文章
文章代碼(AID): #1AGaLpXr (C_and_CPP)