李德財臺灣大學:電子工程學研究所蔡君宏Tsai, Chun-HungChun-HungTsai2010-07-142018-07-102010-07-142018-07-102008U0001-1707200813291100http://ntur.lib.ntu.edu.tw//handle/246246/189119在這篇論文中，我們完成了一個利用假設檢定來判斷雙母體之間是否存在顯著差異的演算法效能評估系統。給定一個要測試的集合與兩個要比較的演算法，我們可以藉由抽樣的方式來推論兩個母體的平均執行時間。主要的理論基礎是利用常態分佈的特性並採用z檢定來測試兩個演算法之間的差異。如果我們可以容忍系統執行完畢後所計算出來的錯誤機率，那麼我們就不需要去對集合中的每一個例子都進行測試。我們同時測試了三個處理二維凸多邊形問題的演算法，利用這個演算法效能評估系統得到了一些實驗結果。In this thesis, we have completed a benchmark system with hypothesis test of two populations. Giving an instance set as the population and two algorithms, we can infer the average executing-time on computers of two algorithms by sampling. The test method used is the z test in statistics and the main analysis is based on the normal distribution. We need not to test each instance in the set if we can tolerate the risk calculated from this benchmark system. We consider three algorithms for computing the 2D convex hull for a set of points in the plane as case study and have obtained some experimental results using the OpenCPS benchmark system.口試委員會審定書……………………………………………………………… i謝……………………………………………………………………………… ii文摘要………………………………………………………………………… iii文摘要………………………………………………………………………… ivhapter 1. Introduction………………………………………………………….... 1hapter 2. Hypothesis Test……………………………………………………… 7 2.1 Introduction……………………………………………………………… 7 2.2 Sampling Methods……………………………………………………… 8 2.3 Normal Probability Distribution………………………………………… 9 2.4 Linear Combination of Random Variables and Sampling Distributions of Means…………………………………………………………………… 14 2.5 Steps of a Hypothesis Test……………………………………………… 16 2.6 Implement on a Benchmark System……………………………………… 23hapter 3. Environment of Benchmark System………………………………… 25 3.1 OpenCPS Benchmark Architecture……………………………………… 25 3.2 Design of the Benchmark System with Hypothesis Test………………… 26 3.3 The Workflow of Executing a Benchmark Task………………………… 27hapter 4. Case Study…………………………………………………………… 31 4.1 Introduction………………………………………………………………. 31 4.2 Definition of Convex Hull Problem……………………………………… 31 4.3 Algorithms to Solve Convex Hull Problem……………………………… 32 4.4 Description of Experiment……………………………………………… 37 4.5 Experimental Results…………………………………………………… 41 4.6 Summary………………………………………………………………… 49hapter 5. Conclusion…………………………………………………………… 52eferences………………………………………………………………………… 53ppendix A……………………………………………………………………… 54ppendix B……………………………………………………………………… 55ppendix C……………………………………………………………………… 571261452 bytesapplication/pdfen-US假設檢定效能評估演算法抽樣執行時間hypothesisbenchmarkalgorithmsamplingexecuting-timethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/189119/1/ntu-97-R95943166-1.pdf