[理工] [資結] 稀疏矩陣&二次方探測

[dunkjames (Firefighter)]

if we store a n by n sparse matrix with non-zero entries by several lists.

In the worst case, the multiplication of two such sparse matrices takes ___?

ANS:  O(n^3)  why?

是非題, 承上, 將worst改成best則為 O(n^2) ANS:解答沒

PS:那有average case嘛?

===============================================================

Consider quadratic probong:

Deleting an element given its key can be done in _____ time in the worst case.

ANS: O(1) why?  改成best avg答案會變嗎

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.80.208.33
※ 編輯: dunkjames       來自: 111.80.208.33        (02/02 01:45)
推 pikachu123:當矩陣滿滿的就跟原本矩陣乘法一樣就O(n^3)
→ pikachu123:sparse的時候C=AxB best是O(A的行數*A的非零元數個數+
→ pikachu123:B的列數*B的非零元數個數) 差不多就n^2
→ pikachu123:這個是DS 聖經習題
推 onlyeric23:第二個best下去就新世界了 /誤
→ dunkjames:矩陣那題我知道了 那麼探測那題是不是best worst avg
→ dunkjames:答案都是O(1) 因為探測的時間都算是常數(?)