iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 18
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 18

Day 18: 線上計算模型(五)Online Algorithms, Part 5 -- 檔案排列問題

如果現在有一個大小為 2N 的空陣列,然後連續進行加入 N 筆資料的操作。這些資料都有一個主要的鍵值可以拿來比較大小。但是插入資料的順序並不固定。在資料逐漸一筆一筆加入這個陣列的過程裡,可能隨時會有人來按照順序存取這些資料,所以我們會希望來存取時,這些資料在陣列裡面都按照順序排得好好的。

找出欲插入的資料要接在哪兩個資料中間,這件事情是容易的。於是我們可以假定,每一次操作都形如「緊接著在 x 後面插入 y」這樣的動作。此外,每一筆資料插入後,資料不一定要連續地擺在一起,但是從左到右必須要按照順序。我們可以在過程中移動資料。

在最壞情形下,最小的總搬移資料次數為何?

下面這篇文章告訴你說可以作到 https://chart.googleapis.com/chart?cht=tx&chl=%20O(N%20%5Clog%5E2%20N) 的時間!大致的概念是,我們在陣列上面覆蓋一些區間,每一次插入以後,我們找出過度擁擠的區間,然後把他們重新等距離排好。這個概念其實跟另一種自毀型(?)二元搜尋樹:代罪羔羊樹(Scapegoat Tree) 概念相同,當一個子樹其數量與深度不成比例時,就把整棵子樹砍掉重練。這麼一來就可以作到 O(log N) 均攤複雜度了!

參考資料

https://courses.csail.mit.edu/6.851/spring07/scribe/lec20.pdf


上一篇
Day 17: 伸展樹與配對堆——驚人的對應關係?
下一篇
Day 19: 線剩計算模型(六)Online Algorithms, Part 6 -- 競爭力分析
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言