iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 19
1
自我挑戰組

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

Day 19: 線剩計算模型(六)Online Algorithms, Part 6 -- 競爭力分析

如果能夠事先得知未來的所有 update,設計出對應的演算法,這就叫做「離線演算法」。顯然在能夠得知未來 update 的情形下,總是可能得出更有效率的演算法。這給予我們另一種能夠刻畫線上演算法效能的一種方式:如果對於一組擁有 m 次更新的輸入來說,若將 update 逐一餵給一個線上演算法,其總時間複雜度為 A、而最好的離線演算法所需要的時間複雜度為 B 的話,我們就說這個線上演算法是 A/B-competitive 的。

在這樣的評估方法中,我們不在意「絕對的效率」,有些特定的輸入可能會導致你的程式花費 O(m^2) 時間、有些可能很有效率,只要 O(m) 時間。但是在特定的競爭力保證下,我們可以說不管程式跑得快或跑得慢,它與最好的離線演算法不會差距太大。

經典的競爭力分析可以用在以下三個題目:

一、滑雪板租借問題 Ski Rental

一個滑雪場每天租滑雪板要花 X 元。如果你購買滑雪板要花 Y 元。悲慘的是,你事先不知道你會去滑雪幾天XD 請問你有沒有一套租雪版的策略,使得花費的錢「相對於」已知要去滑雪幾天的情形下,不會差距太多?

二、自調整鍊結串列存取問題 Self-Adjusting Linked List

你有一個單一鍊結串 Linked List,每一次存取都只能從頭開始存取。現在你想要進行一連串的 m 次查找:每一次查找,你可以沿著這個鍊結串列一路走下去,而花費的時間就是你經過了幾個節點。而查找完畢以後,你唯一能做的操作就是「對於你存取過得某個節點,交換他以及他的下一個節點」。你可以重複很多次操作。請問能否設計一個線上演算法,使得經過 m 次查找以後,總花費時間與「已知未來的 m 次查找時的離線演算法」,其總時間不會差距太多?

三、探戈樹 Tango Tree

這個是 Erik Demaine 以及 Pătrașcu 等人設計出的線上版二元搜尋樹。他們利用了 Link-Cut Tree 的概念設計出了每一次更新都不會比「最好的二元搜尋樹離線算法」差 O(log log n) 倍時間的資料結構,神猛一陣。

而競爭力分析可以追朔到在線上計算模型中的最大 Open Problem:

Conjecture:

伸展樹在所有二元搜尋樹裡頭是 O(1)-competitive 的。

解出來應該就會留名清史。

參考資料


上一篇
Day 18: 線上計算模型(五)Online Algorithms, Part 5 -- 檔案排列問題
下一篇
Day 20: 隨機計算模型 Randomized Algorithms -- 快速排序法
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言