排序在電子計算機科學中(Computer science), 占有相當重要的地位, 它的應用很廣
, 據統計早年幾乎占了計算機一半的操作時間, 目前也還占四分之一以上。其最早的
研究是1945年Von Neumann 的研究, 稍后無數的論文探討排序的問題。
排序是將一任意數列(Sequence)輸入電子計算機后, 利用一演算法(algorithm) 將數
列內的元素由小到大或由大到小排列, 形成一完全排序數列。因此, 如何快速排序,
與演算法有密切的關系。早期, 許多有效的排序演算法被發現。
而每一演算法皆有它的特長, 所以我們無法找到一uniformly optimal algorithm;也
就是說, 沒有一演算法對任一數列都是最佳的(optimal);最佳就是排序速度較快。
而對一具體數列如何尋找它最有效的演算法? 辦法就是利用事前測量。
事前測量是衡量一個給定的數列與完全排序的數列之間的差別程度。因為對於所謂的
差別有許多不同的觀點, 所以事前測量有許多種。針對一種事前測量有所謂的相對應
的最佳演算法(optimal algorithm),使得當此種事前測量值較小時, 用此相對應的最
佳演算法, 能快速排序。
但如何判斷事前測量的值是否較小? 最徹底的辦法就是求出事前測量的分配或均值與
均方差。
本篇最主要在求兩種事前測量,osc及ma的均值與均方差。