[非關] 資結演算法獵人
我最近在寫資結考古題遇到了一個問題弄得我心好亂
不知道我的想法對不對 所以想問問看大家的意見 謝謝！
-------------------------------以下是題目-------------------------------
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
推
12/27 23:48, , 1F
12/27 23:48, 1F
→
12/27 23:49, , 2F
12/27 23:49, 2F
推
12/27 23:49, , 3F
12/27 23:49, 3F
→
12/27 23:51, , 4F
12/27 23:51, 4F
→
12/27 23:52, , 5F
12/27 23:52, 5F
→
12/27 23:52, , 6F
12/27 23:52, 6F
→
12/27 23:54, , 7F
12/27 23:54, 7F
推
12/27 23:57, , 8F
12/27 23:57, 8F
→
12/27 23:57, , 9F
12/27 23:57, 9F
→
12/27 23:59, , 10F
12/27 23:59, 10F
→
12/28 00:00, , 11F
12/28 00:00, 11F
→
12/28 00:11, , 12F
12/28 00:11, 12F
推
12/28 00:36, , 13F
12/28 00:36, 13F
推
12/28 00:44, , 14F
12/28 00:44, 14F
→
12/28 00:45, , 15F
12/28 00:45, 15F
→
12/28 00:49, , 16F
12/28 00:49, 16F
→
12/28 00:50, , 17F
12/28 00:50, 17F
→
12/28 00:50, , 18F
12/28 00:50, 18F
→
12/28 11:10, , 19F
12/28 11:10, 19F
→
12/28 11:10, , 20F
12/28 11:10, 20F
→
12/28 14:07, , 21F
12/28 14:07, 21F
→
12/28 15:03, , 22F
12/28 15:03, 22F
Hunter 近期熱門文章
PTT動漫區 即時熱門文章
13
16