: 推 ephesians:确定吗?既然是硬体,为什麽不是组合逻辑运算,而是loop? 06/22 12:15 : → ephesians:硬体上,shift n是多个运算,或是一个运算? 06/22 12:18 : 推 jeunder:抗议! 为何 address 的 O(logn) 加法就可以视为 O(1) ? 06/22 12:28 : → jeunder:为何 node 编号的 O(logn) shift 就要视为 O(logn) ? 06/22 12:29 : 推 ephesians:这样想起来很可怕,以後要算时间复杂度可麻烦了, 06/22 13:05 : → ephesians:要从基本逻辑计算开始一条条算 06/22 13:05 : 推 ledia:shift logn 可以很大呀, 不一定是一次 inst. 就做得出来的 06/22 13:16 : → ledia:而且你要比较演算法 本来就需要在公同 model 上 06/22 13:17 : → ledia:定什麽样的 model 只是让大家方便吧 想要不一样的也行呀 06/22 13:17 : → ledia:如果你们不能接受我的说法 去看书的解释吧 :p 06/22 13:18 : 推 march20:别的不说, 光 shift 100, 200 就不是一般处理器能一次做的 06/22 13:17 : 推 ephesians:你的说法是来自於书上? 06/22 13:24 : 推 ledia:我的文章.... 有这麽难看懂吗? 第一句? @@? 06/22 13:31 : → ledia:还是你直接跳过第一段? XD 06/22 13:31 : 推 ephesians:但你後面的解释也是从书里来的?(我的问题有那麽难懂吗?) 06/22 13:41 : → ephesians:我是指你将他曲解为巧妙躲开的那句 06/22 13:45 : 推 ledia:你还没看到书上说什麽 就说我曲解是不是不很恰当呢? 06/22 13:52 : → ledia:巧妙的躲开的确是我自己的说法, 因为这是避免演算法分析 06/22 13:53 : → ledia:还要牵扯太多复杂的 addressing 的问题的缘故 06/22 13:54 : 推 ledia:既然你今天讨论的是演算法问题, 本来就需要个基准点 06/22 13:56 : 推 ephesians:我并没下定论,但也该表达我的质疑 06/22 15:10 : → ephesians:另外我不认为基准点可以一下子高层一下子低层 06/22 15:11 http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK/NODE12.HTM 这里有一段说得很好: Every model has a size range over which it is useful. Take, for example, the model that the earth is flat. You might argue that this is a bad model, since the earth is not flat. However, when laying the foundation of a house, the flat earth model is sufficiently accurate that it can be reliably used. Further, it is so much easier to manipulate a flat-earth model that it is inconceivable that you would try to think spherically when you don't have to. 并不是说基准点可以一下高一下低. 就像在讨论量子力学时, 你还要拿古典力学来当基 准, 那保证是拿石头砸自己脚. 同样的, 在讨论古典力学时, 偏偏要计入相对可以忽略 的强作用力弱作用力, 那根本是没事找事做. 回到原来的 case. 一般来说, 我们常用的资料型别就足以处理大部份问题了, 在这情况 下, 我们把 memory access 当成是 O(1), 对这些资料作四则运算, 或是作有效位数内的 shift 都可以看成是 constant time. 今天遇到的问题有可能会 shift(100), shift(200), 甚或是 shift(10^10), 这时候再说 shift 是 constant time 就没道理 了. (如果这样也可以当 constant time 来讲, 那以後演算法都不用教 bignum 好了 XD) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 71.136.243.18 ※ 编辑: march20 来自: 71.136.243.18 (06/22 16:20) ※ 编辑: march20 来自: 71.136.243.18 (06/22 16:21)