分解隨機Cayley樹所需複雜度的極限分布

Abstract

在計算科學中，常常需要處理將集合合併的問題，而為了有效率的解決這個問題，需要建造適當的的資料結構和相對應的演算法，這類的問題又稱為"Union-Find problem"﹔事實上，已經有許多種不同的資料結構和相對應的演算法被提出來以解決這個問題，為了了解各個方法的優劣，我們考慮最簡單的狀況，也就是將n 個不同的元素兩兩合併，直到成為一個集合為止所需的複雜度。在這篇論文中，我們假設每個合併過程所需的複雜度是被合併的兩個集合的大小之和的冪次方，求其在隨機生成樹的機率模型底下，所需總複雜度的極限分布。 在這裡，我們使用一個近幾年才發展出來的新工具，稱為奇異點分析(Singularity Analysis)﹔這個工具可以讓我們直接由生成函數的漸進展開式得到生成函數係數的漸進式。我們將使用這個方法來計算總複雜度的各階動差，進而再利用動差法推導出總複雜度的極限分布。 這篇論文的一開始，也就是第一章我們先介紹問題的背景並給出我們研究的結果﹔在第二章我們介紹我們研究所使用的工具，也就是奇異點分析﹔而第三章是這篇這篇論文最主要的部分，我們利用奇異點分析導出複雜度的期望值和各階動差並在第四章利用動差法證明了我們的結果﹔最後在第五章我們對整篇論文做一個總結。

In computer science, the so-called "Union-Find problem" is concerned with establishing a data structure for maintaining a collection of disjoint sets such that the process of merging sets can be carried out efficiently. Indeed, several data structures and corresponding algorithms for merging sets have been proposed. For the purpose of comparing the complexity of these algorithms, it is naturally to consider the total cost incurred from merging n singleton sets into one set. In this thesis, we assume that the cost of each merging step is the power of the sum of the sizes of the sets being merged and then derive the expected value and the limiting distribution of the total cost under the random spanning tree model. The main tool used in this thesis is singularity analysis, which is a method connecting the asymptotics of generating functions with the asymptotics of their coefficients. We will use it to derive the moments of each order. Then, with the method of moments, the limiting distribution of the total cost will follow. In the first part of this thesis (Chapter 1), we introduce the problem of interest and state the results of our work. In Chapter 2, we give an introduction about our main tool, singularity analysis. The central part of this thesis, namely Chapter 3, is devoted to the derivation of the expected value and higher moments. These results will will then be used in Chapter 4 for prove our main result. Finally, we end the thesis with a conclusion in Chapter 5.