作者c5onb (大邱)
看板Hunter
標題[非關] 資結演算法獵人
時間Thu Dec 27 23:27:46 2012
我最近在寫資結考古題遇到了一個問題弄得我心好亂
不知道我的想法對不對 所以想問問看大家的意見 謝謝！
-------------------------------以下是題目-------------------------------
Suppose sparse matrices are on average of size n by n with m non-zero entries
(n < m < n^2), and we store a sparse matrix by several lists: one list per
row.
(A) The space complexity of one such sparse matrix.
(B) The average time complexity of accessing an entry.
(C) The time complexity of accessing an entry in the worst case.
(D) The average time complexity of accessing all entries of a row.
(E) The average time complexity of accessing all entries of a column.
-------------------------------以上是題目-------------------------------
我的想法：
─
─
─
│
─
│
n . .
. .
rows . .
│
─
─
total m elements
(A) space complexity:
n個紅點 +
m個黃點 = Θ(n + m)
(B) accessing one entry on average:
一定有一個entry只要找一次 一定有一個entry要找兩次 找三次... 找m次
1 + 2 + 3 + ... + m
∴ Θ(───────────) = Θ(m)
m
(C) accessing one entry in the worst case:
最糟就是要找的是最後一個entry 所以全部都看了一遍
∴ Θ(m)
(D) accessing a row on average:
令 m(i) 為第i個row所有的entries數量
則所求為
m(1) + m(2) + m(3) + ... + m(n)
Θ(────────────────) = Θ(m / n)
n
(E) accessing a column on average:
每一個entry都看過一遍 檢查他是不是在這一個column裡面
∴ Θ(m)
以上 麻煩大家了！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.110.136.216
推 StarTouching:忘記滿多的 不過我有幾個問題先 12/27 23:48
→ StarTouching:(B) 是否涵蓋 zero entry (也是滿費時的) 12/27 23:49
推 coconutman:(A) 依照你的實作方式是對的。 12/27 23:49
→ StarTouching:(C) worst case當然是最後一列全部都非零 2n 12/27 23:51
→ coconutman:(B) 基本上你應該可以快速知道entry在那個row，透過 12/27 23:52
→ coconutman:index計算或hash。所以Average 我覺得是Θ(n)。 12/27 23:52
→ coconutman:不然你這複雜度和linked list的沒兩樣。 12/27 23:54
推 coconutman:(C) 同樣argument... 12/27 23:57
→ coconutman:(E) 我覺得你考慮的是 worst case不是 average case～ 12/27 23:57
→ coconutman:求複雜度應該要提供一下演算法喔。不然不同實作方式， 12/27 23:59
→ coconutman:求出來會不太一樣。 12/28 00:00
→ c5onb:可是題目就只有這樣出啊QQ 12/28 00:11
推 chigi:忽然覺得我的資結跟廢物一樣 XD 12/28 00:36
推 coconutman:沒有怪你的意思呀！他會這樣出應該是某教科書有標準的 12/28 00:44
→ coconutman:作法。不過我覺得這樣問比較沒意義而已。^^ 12/28 00:45
→ henry1234562:正常來說 問複雜度就要提供相應的演算法吧 12/28 00:49
→ henry1234562:不過如果是我以前老師 他會直接給你複雜度 12/28 00:50
→ henry1234562:然後要你寫出那複雜度的演算法.. 12/28 00:50
→ chigi:推樓上 我也這樣覺得,沒給演算法卻叫人算複雜度怪怪的 12/28 11:10
→ chigi:怎麼可以預設別人已經都知道演算法呢? 又不是什麼有名的algo 12/28 11:10
→ kib65060:單純 access queue 需要什麼演算法? 不就traverse.... 12/28 14:07
→ keepoo:這題應該是有預設用什麼標準作法 所以 去看課本吧 12/28 15:03