線性醢序的零存攤付式分析

Abstract

零存攤付式分析是近幾年來所發展的一種分析演算法的新技術，它用來分析一連串ｍ 個運算的最壞情況的時間。而線性醢序是一種不用目錄的動態檔案結構，它可隨檔案 中資料的多寡改變檔案中儲存頁的數量，以達到增加共用率及減少重新分配資料時的 負擔。 本篇論文中提出了線性醢序中分配運算的零存攤付式分析。我們證明了無控制策略的 線性醢序分配運算之攤付式執行時間將被限制在８次磁碟存取之下，甚至在連一個資 料均不能被重新分配的最壞狀況下亦然。而當每一運算均有１╱ｂ之分配率時（其中 ｂ表主要儲存頁的容量大小），將可達到約將近５ｍ次磁碟存取。在相同的分配率假 設下，這個結果很接近一些其他必需靠目錄之動態醢序方法的分配運算之執行時間。 也就是說，以零存攤付式的角度來看，無控制策略的線性醢序能提供相同的分配功能 ，而不需任何的目錄幫助。