1樓：「已登出」
原演算法：
for(1:M.mu)
for(M.rpos[arow]:tpfor(N.rpos[brow]:t)
[注]最後乙個for迴圈是壓縮處理，故不考慮。
tp:第arow行的非0元個數+1；
t: 第brow行的非0元個數+1
所以時間複雜度即：M的行數×M的每行的非0元個數×N的每行的非0元個數。
轉化一下就是書上的了。
另：平均複雜度是指所有可能輸入例項在等概率出現的情況下，演算法的期望執行時間。書上好像沒有對輸入進行特殊化處理吧，複雜度求的是數量級，不是具體數。
2樓：紙杯蛋糕
Z.δ = Z.tu/(Z.mu*Z.nu) 稀疏因子代表mu*nu的矩陣Z中非零元素分布程度。
Z.tu為矩陣中非零元素個數。
所以M.tu = M.δ * M.
nu * M.muN.tu = N.
δ * N.nu * N.muN.
tu/N.nu = N.nu * N.
δ = N.tu/(N.mu)
即 N矩陣中每行平均有幾個非零元素
同理 M.nu * M.δ = M.tu/(M.mu)即 M矩陣中每行平均有幾個非零元素
看三個for巢狀，()內就不寫了
for(arrow = 1; arrow <= Mu; i++)// O(M.mu)
for(M矩陣arrow行有幾個非零元素)// O(M.nu*M.δ)
for(N矩陣brow行有幾個非零元素)
//O(N.nu*N.δ)
三個O相乘得出O(M.tu*N.tu/N.mu)不是平均情況的原因:
個人認為
是因為時間複雜度度量，
多個for巢狀時相對裡層for 的迴圈次數平均為(N.nu*N.δ)。
而可以知道由於外層for的影響可以把這個迴圈次數的O 近似成O(N.nu*N.δ)。
(類似每款遊戲平均時間 * 遊戲數 = 總遊戲數這種感覺)
3樓：BeriaL
我的理解是
1、即使不平均，算出的最終結果仍然是這個
因為該演算法本身只是為了走完所有的非0元並運算，與非0元所處位置無關。
假如N矩陣非0元全部在最後一行或者全在第一行，我仍然是要將N矩陣走N.mu遍的（for（p）），那麼最後算起來每遍（即每行）我還是相當於走了N.tu/N.
mu個元素。（突然想到可以參考瞬時速度和平均速度）
2、假如最壞情況，唔，看了看演算法中幾個for迴圈的判定，for（arow），判定M.mu
for（p），判定tp，tp為M陣本行非0元末尾for（q），判定t，t為N陣本行非0元末尾for（ccol），判定Q.nu，即N.nu沒有變數。。。
嚴蔚敏 的 《資料結構 C語言版 》 這本書在豆瓣評分為什麼不高？
木靈Rin 咱的資料結構是用大理石封面的 資料結構與演算法分析 C 學的。今日看北理考研真題，有一道題是 對乙個已經正序排列的陣列進行快速排序的時間複雜度是多少？答了O nlogn 但答案是O n 2 不解。後來一查，考研大綱是根據嚴資料結構書的，嚴資料結構書中快速排序是固定取front為pivot...
《資料結構與演算法分析C語言描述》真的適合初學者嗎
看前言 本書適合作為高階資料結構 CS7 課程或是研究生第一年演算法分析課程的教材。學生應該具有中等程度的程式設計知識，包括像指標和遞迴這樣一些內容，還要具有離散數學的某些知識。 法布 初學者看這個會覺得很吃力，注意看一下這本書前言中的介紹 本書適合作為高階資料結構 CS7 課程或者研究生第一年演算...
資料結構和演算法先以C語言開始學習好還是按照自己學的語言開始
龍馬精神 看現在招聘，公司的要求。大致感覺是c python。學了c以後，很多底層的東西可以理解了，我覺得這樣對培養乙個計算機程式設計從業者的意識很重要。也許以後你用到高度封裝的產品，不需要你了解到底層。但我覺得，有了c的基礎，再去理解一些其他的語法現象會比較容易，畢竟c生萬物，很多東西說到底就是c...