作者ledia ()
站内Prob_Solve
标题Re: [问题] ancestry problem
时间Fri Jun 22 09:50:15 2007
※ 引述《jeunder ()》之铭言：
: ※ 引述《march20 ()》之铭言：
: : 对整数 shift n bits 确实是 O(1), 但如果这颗树的高度是 100, 200,
: : (一代单传的树, 然後传 100 或 200 代就是了, 并不难造 XD)
: : 或怎更多时, 铁定不是 O(1) 可以完成的 XD
: 所以说在没有对 array 做 preprocessing (例如: sorting...) 的情况下
: 要在 array 里面 search 某个东西... 是 O(nlogn) 罗? XD
: 怎麽说? 因为对 array 里面的项目定址需要用到 O(logn) 个 bits,
: 而依序 search n 个项目, 每次都要对位址做 O(logn) bits 的加法,
: 所以 array search 是 O(nlogn) ?
: 按照你的说法, 如果 array 里面的元素数量是一兆, 两兆或更多时,
: 位址的运算铁定不是 O(1) 可以完成的 XD
这也就是为什麽很多 complexity/algorithm 的书籍
开宗明义会先说清楚他们在什麽 model 上讨论问题
像是许多书用的就是 random access machine (RAM) model
RAM model 的其中一个条件就是
* Each memory access takes exactly one time step, and we have as
much memory as we need. The RAM model takes no notice of whether
an item is in cache or on the disk, which simplifies the analysis.
巧妙的躲开了定址所需要的 O(logn) 的问题
但是 shift logn bits 仍然是用 loop 做出来的
则应该还是需要花 O(logn) 的时间
--
有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。
存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你
，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也
是比较不容易被击倒的人。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.56
※ 编辑: ledia 来自: 140.112.30.56 (06/22 09:50)
1F：推 ephesians:确定吗?既然是硬体,为什麽不是组合逻辑运算,而是loop? 06/22 12:15
2F：→ ephesians:硬体上,shift n是多个运算,或是一个运算? 06/22 12:18
3F：推 jeunder:抗议! 为何 address 的 O(logn) 加法就可以视为 O(1) ? 06/22 12:28
4F：→ jeunder:为何 node 编号的 O(logn) shift 就要视为 O(logn) ? 06/22 12:29
5F：推 ephesians:这样想起来很可怕,以後要算时间复杂度可麻烦了, 06/22 13:05
6F：→ ephesians:要从基本逻辑计算开始一条条算 06/22 13:05
7F：推 ledia:shift logn 可以很大呀, 不一定是一次 inst. 就做得出来的 06/22 13:16
8F：→ ledia:而且你要比较演算法 本来就需要在公同 model 上 06/22 13:17
9F：→ ledia:定什麽样的 model 只是让大家方便吧 想要不一样的也行呀 06/22 13:17
10F：→ ledia:如果你们不能接受我的说法 去看书的解释吧 :p 06/22 13:18
11F：推 march20:别的不说, 光 shift 100, 200 就不是一般处理器能一次做的 06/22 13:17
12F：推 ephesians:你的说法是来自於书上? 06/22 13:24
13F：推 ledia:我的文章.... 有这麽难看懂吗? 第一句? @@? 06/22 13:31
14F：→ ledia:还是你直接跳过第一段? XD 06/22 13:31
15F：推 ephesians:但你後面的解释也是从书里来的?(我的问题有那麽难懂吗?) 06/22 13:41
16F：→ ephesians:我是指你将他曲解为巧妙躲开的那句 06/22 13:45
17F：推 ledia:你还没看到书上说什麽 就说我曲解是不是不很恰当呢? 06/22 13:52
18F：→ ledia:巧妙的躲开的确是我自己的说法, 因为这是避免演算法分析 06/22 13:53
19F：→ ledia:还要牵扯太多复杂的 addressing 的问题的缘故 06/22 13:54
20F：推 ledia:既然你今天讨论的是演算法问题, 本来就需要个基准点 06/22 13:56
21F：推 ephesians:我并没下定论,但也该表达我的质疑 06/22 15:10
22F：→ ephesians:另外我不认为基准点可以一下子高层一下子低层 06/22 15:11
23F：推 ledia:我今天学到意指别人屈解不是下定论 06/22 16:18
24F：→ ledia:不过我一点没有想要说服你, 你觉得不该怎样, 请继续如此想 06/22 16:19
25F：推 ephesians:要人认为你不是曲解,给个证明! 06/22 17:06
26F：→ ephesians:要讲RAM仍是循序运算,你可以列个layout指出它哪里循序 06/22 17:07
27F：→ ephesians:你说不说服我根本不重要,重要的是讲你错的地方你能不能 06/22 17:08
28F：→ ephesians:证明你没有错? 06/22 17:09
29F：推 ledia:是你在曲解 是你应该要提证明吧 XD 06/22 17:29
30F：→ ledia:你能不能证明你没有错? 06/22 17:29
31F：→ ledia:march 也把我看的书的出处也点出来了 06/22 17:30
32F：→ ledia:你如果还想要在这里打转 你自便吧 :p 06/22 17:30