作者ephesians (ephesians)
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Fri Jun 22 17:30:55 2007
※ 引述《march20 ()》之铭言：
(前面的平地球model无济於事,所以省略)
: 回到原来的 case. 一般来说, 我们常用的资料型别就足以处理大部份问题了, 在这情况
: 下, 我们把 memory access 当成是 O(1), 对这些资料作四则运算, 或是作有效位数内的
: shift 都可以看成是 constant time. 今天遇到的问题有可能会 shift(100),
: shift(200), 甚或是 shift(10^10), 这时候再说 shift 是 constant time 就没道理
: 了. (如果这样也可以当 constant time 来讲, 那以後演算法都不用教 bignum 好了 XD)
讲了半天仍然内定 shift(n) = shft(n-1) + shift 1,
但我就是质疑,shift计算真的是上述式子吗?
在上述式子中,你所讲的shift当然是循序的.
但问题是我就是要拆你的台,我所谈的并不是基於上述数学式子,
而是以别的计算方式为主,譬如 sfift(n) = (A & B) | (C & D)
我算shirt(1)是这个逻辑式子,算shift(2000)照样是这个逻辑式子,
并没有因为n变得多大,式子的计算量就变大.
软体层面,你假定一个数学计算model没问题.
但RAM它是硬体,请不要用软体的思维去假想它是怎麽运作的.
也许硬体中真的就是O(1),却被不知硬体的人假想为软体的加加减减,
那这样子random access这个名字变得没有意义了,
就像前前文随意讲的一句话:
"(RAM model书上的解释)巧妙地躲开定址所需要的O(logn)问题"
这话有什麽根据?
你可以这样假想,但这假想的东西跟硬体实际情况相冲的时候,
我就可以觉得你讲得荒谬,而要你提出具体说明.
万一它不是呢? 这时候你可能又说,反正只是我的model,与实际情况不合没关系.
但问题是,因为那句未经证实的话,
许多人可能会被误导,而开始思考 a[65535] = 65 这一行程式是O(1)还是O(n)!!!
这很可怕啊!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.114.106
1F：→ ledia:RAM model 不是硬体 是 model ... 可以去看一下书吗? XD 06/22 17:32
2F：→ ledia:我是不知道为什麽你这麽爱现在硬体能做到什麽扯上关系 06/22 17:32
3F：→ ledia:也许是你以为这里的 RAM 是 random-access memory 06/22 17:32
4F：→ ledia:但是这是演算法在比较时所需要的一个基准点 06/22 17:33
5F：→ ledia:定好哪些东西是 unit cost, 哪些不是 06/22 17:33
6F：→ ledia:这样演算法才能互相比较 06/22 17:34
7F：→ ledia:如果真的要讲硬体 shift(2000) 和 shift(1) 的 2000,1 06/22 17:34
8F：→ ledia:bit 数也不会一样呀 06/22 17:35
9F：→ ledia:也就是你的 A, B, C, D 的 bit 数并不相同 06/22 17:35
10F：→ ledia:如此失焦下去, 什麽时候才能开始讨论演算法呢? 06/22 17:35
11F：推 ledia:最後... 我想讲到这你再不同意 我也掰不出别的了 06/22 17:39
12F：→ ledia:所以我就此打住 也让板主方便 ^^: 06/22 17:39
13F：推 ephesians:我讲的是random access memory 06/22 17:57
14F：→ ephesians:你还可以回答我a[65535]是一个动作还是65535个动作? 06/22 17:57
15F：→ ephesians:A,B,C,D是随便举例的,你还真的讨论bit数,我昏了 06/22 17:59