※ 引述《ephesians (ephesians)》之铭言： : ※ 引述《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) 呃, 不管你要用什麽逻辑式子, &, +, -, *, % 组成的式子, 原来 operand 是多少 bit 最糟情况结果至少就是那麽多 bit. 所以如果 n 够大, 计算量还是会变大的. (除非你做 f(n) = n - n 这种事 XD) : 我算shirt(1)是这个逻辑式子,算shift(2000)照样是这个逻辑式子, : 并没有因为n变得多大,式子的计算量就变大. : 软体层面,你假定一个数学计算model没问题. : 但RAM它是硬体,请不要用软体的思维去假想它是怎麽运作的. : 也许硬体中真的就是O(1),却被不知硬体的人假想为软体的加加减减, 这个, 能不能给个, 不论 A, B 多大, A << B 都是 constant time 的 CPU 给我, 我来去买一个 XD : 那这样子random access这个名字变得没有意义了, : 就像前前文随意讲的一句话: : "(RAM model书上的解释)巧妙地躲开定址所需要的O(logn)问题" : 这话有什麽根据? : 你可以这样假想,但这假想的东西跟硬体实际情况相冲的时候, : 我就可以觉得你讲得荒谬,而要你提出具体说明. 对, 你得到他了, 当一个 model 在某个 case 跟实际情况差太多时我们就不该用他, 这就是为什麽在这里我们不能继续把 shift 当成 O(1) 的原因, 因为跟硬体实际情况冲突了 : 万一它不是呢? 这时候你可能又说,反正只是我的model,与实际情况不合没关系. : 但问题是,因为那句未经证实的话, : 许多人可能会被误导,而开始思考 a[65535] = 65 这一行程式是O(1)还是O(n)!!! : 这很可怕啊! --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 71.136.243.18 ※ 编辑: march20 来自: 71.136.243.18 (06/23 01:37)