一種新的動差法與其應用

Abstract

演算分析在計算科學裡是一個重要的工作，這可以幫我們了解這 些演算法適當的用途。在這篇論文中，我們將會用機率的理論來了解 一個演算法所須要運行的時間。為了使這樣機率的方法可以運作，首 先我們考慮演算法的輸入為一個適當的隨機模型，然後讓運行的時間 成為隨機變數，這樣我們就可以嘗試算出它的期望值和變異數，進而 去了解取極限後的行為。在最近幾年，method of moments 已經變成 了解決這些問題的標準工具。

在論文中，我們對一個叫優先樹的資料結構和它們的分析感到興 趣，也會使用method of moments來簡化最近一些優先樹結果的證明。 然而，在使用這個方法的過程中，我們會遇到一些困難，此時，我們 將會介紹一個新的method of moments 來解決這些問題。

以下是我們的論文概述，在第一章，我們將會介紹method of moments，並且也會介紹優先樹和關於這資料結構近幾年的結果。第 二章，我們會用一個新的method of moments 重新證明第一章所提到 的一個結果。第三章，我們再一次使用這方法來解決一個比較複雜的 問題。最後在第四章會給一個結論。 中

Analyzing algorithms in order to understand their usefulness and appropriateness is a key task in computer science. In this thesis, we will use probability theory to analyze the running time of algorithms. In order to perform such a probabilistic analysis, we will first fix a suitable random model for the input. Then, the running time becomes a random variable and properties such as the mean value and the variance are sought. Once the latter properties are understood, one also wants to clarify the limit behavior. In recent years, the method of moments has become a standard tool for this purpose.

In this thesis, we are interested in a data structure, called priority trees, and their analysis. One of the goals of the thesis is to simplify the proofs of some recent results on priority trees by using the method of moments combined with asymptotic transfers. However, in doing so, some new problems will arise which we will overcome by introducing a new variant of the method of moments.

We give a short outline of the thesis. In Chapter 1, we are going to introduce the method of moments. Moreover, we will introduce priority trees and explain some recent results concerning this data structure. Then, in Chapter 2, we will introduce our new method and re-prove some of the results mentioned in Chapter 1. In Chapter 3, we will apply our new approach to a more complex example. We will end the thesis with a short summary in Chapter 4.