標題: 線性醢序的零存攤付式分析
作者: 錢炳全
GIAN, BING-GUAN
楊維邦
YANG, WEI-BANG
資訊科學與工程研究所
關鍵字: 線性醢序;零存攤付式;動態檔案結構;無控制策略;分配率
公開日期: 1988
摘要: 零存攤付式分析是近幾年來所發展的一種分析演算法的新技術,它用來分析一連串m 個運算的最壞情況的時間。而線性醢序是一種不用目錄的動態檔案結構,它可隨檔案 中資料的多寡改變檔案中儲存頁的數量,以達到增加共用率及減少重新分配資料時的 負擔。 本篇論文中提出了線性醢序中分配運算的零存攤付式分析。我們證明了無控制策略的 線性醢序分配運算之攤付式執行時間將被限制在8次磁碟存取之下,甚至在連一個資 料均不能被重新分配的最壞狀況下亦然。而當每一運算均有1╱b之分配率時(其中 b表主要儲存頁的容量大小),將可達到約將近5m次磁碟存取。在相同的分配率假 設下,這個結果很接近一些其他必需靠目錄之動態醢序方法的分配運算之執行時間。 也就是說,以零存攤付式的角度來看,無控制策略的線性醢序能提供相同的分配功能 ,而不需任何的目錄幫助。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772394084
http://hdl.handle.net/11536/53841
Appears in Collections:Thesis