作者yoco315 (眠月)
看板C_and_CPP
标题Re: 双层排序问题
时间Wed Jun 24 23:25:37 2009
※ 引述《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
1F：推 softwind:switch case ? 应该是还是 O(n)吧? 06/25 01:50
2F：→ yauhh:没差啦,反正是小事 06/25 02:52
3F：→ yauhh:原po只是问怎麽写,给个方向;但一堆人拼命给越快越好的作法, 06/25 02:54
4F：→ yauhh:这一点我很不能理解. 先给一个适当的作法不就可以了吗 06/25 02:55
5F：→ yoco315:and why did you remark you algo is O(1) -_-|| 06/25 03:12
6F：→ yoco315:(which actually not...) 06/25 03:12
7F：→ yoco315:not to mention the solution is complicated O_O 06/25 03:23
8F：推 Fenikso:写死在code里面的switch case就算有1000000项也是O(1) 06/25 03:42
9F：→ yoco315:It depends on the case value and the compiler. 06/26 00:30
10F：推 Fenikso:no, 1000000 is a constant 06/26 00:37
11F：推 softwind:对於写死的switch是O(1) 我比较有兴趣 compiler有说明吗? 06/26 00:39
12F：→ softwind:或是哪家的compiler有说明? 有人看过的可以share一下 06/26 00:39
13F：推 Fenikso:我想讲的只是.. n是input size, switch的数量并不会因为 06/26 02:20
14F：→ Fenikso:input而改变, 所以就算里面有100000个case也还是constant 06/26 02:20
15F：→ Fenikso:time 06/26 02:20
16F：→ Fenikso:这点yauhh讲的并没有错 06/26 02:21
17F：→ yoco315:这样算的话，那我乾脆说所有的 input 都是有限多的.. 06/26 22:50
18F：→ yoco315:对任何一个问题，我都用 code generator 生出 switch 码 06/26 22:51
19F：→ yoco315:然後交给 compiler 直接 output 答案就好.. 06/26 22:51
20F：→ yoco315:这种论点无异跟白痴一样嘛.. 06/26 22:51
21F：→ yoco315:人家现在讲的就是 case 的数目跟决策的时间.. 06/26 22:52
22F：→ yoco315:好的 compiler 遇到好的 case 可以做出 O(1) 的跳转没错 06/26 22:52
23F：→ yoco315:但是 general case 就不是 06/26 22:52