[理工] [資結] sparse matrix

[assassin88 (Ace)]

一、 O(nlogn) + Θ(nlog^2n) = ？

二、What is the basis idea behind the fast transpose algorithm that we can
    transpose a sparse matrix in O(cols+terms) time.

    請問一下原意是什麼呢？ terms 的理由大概可以知道，但 cols 不知理由為何？

三、Give a BST, how can we make it to support the operation "search for the
    Kth largest element"？ Briefy describe the search algo.

麻煩指導了~感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.78.183
※ 編輯: assassin88      來自: 61.57.78.183         (03/09 08:23)
推 FRAXIS:1. Θ(nlog^2n) 3. 多增加一個size欄位 記錄他的子樹大小
→ privatewind:                                       左
→ privatewind:若是兩邊子樹大小都算的話, 會囧喔
推 Lautreamont:請問是不是每insert node時，在inorder排序在該node
→ Lautreamont:右邊的所有node，它們的size都要加1?
推 FRAXIS:給二樓 我只要看我左子樹的size 不就可以得到左子樹大小
→ FRAXIS:哪裡會出現問題？
→ assassin88:我原本是想說先個別算出左右子數size~再以BST判斷左/右
→ assassin88:然後在到左/柚子樹找第k個..但覺得應該有更直接的方法?