Abstract
由於電子技術之進步，計算模型之日新月異，使得學者正努力朝平行處理之方向邁進。本篇論文的主要目的乃針對三個問題的平行複雜度以及達成此複雜度時所須之處理機個數加以討論。這三個要討論的問題分別是排序問題，線性方程組問題，以及聯結組問題。在排序問題方面，我們提出了三個演算法，一個是陣列的排序法另一個是鏈結串列的排序法。前者所使用的處理機個數隨問題大小呈指數增加，而後者則隨問題大小呈指數的三次方增加。兩者所耗時間均為常數，亦即〞演算法在固定時間內完成〞術語是：0 (1) 。此結果突破了長久以來學者所無法突破的下障：0 (Logn)。因此僅考慮：求速〞時此篇結果確已達到速度的極限並成為本篇論文的最大頁獻。所謂線性方程組就是一般所謂的多元線性聯立方程式，就此問題我們提出之演算法是放在心臟收縮式陣列型機器上執行的。這個演算法是以Melhem君所提的演算法為藍本而加以改進的。原本的演算法是在具有廣播能力之網路上執行的。而我們將其移植在心臟收縮式陣列型機器上去執行是本篇論文另一項小小的頁獻。就時間複雜度而言，我們的演算法與前人之結果相去不遠；然就使用之處理機數目而言，我們比前人少用一點（註：我們比Melhem少用n 個處理機，他用了n (n+3)/2 個，而我們只用了n (n+1)/2 個，在此n 為聯立方程式的個數）。在聯結組問題方面，我們改進了Shiloach君及Vishkin 君所提之演算法，使處理機數目由原本之n+2m降為m ，其中n 是輸入之圖形上的頂點個數，而m 是其邊的數目，在速度方面上述二君所提之演算法之複雜度僅為0 (Log n )，而吾等所提之演算法經嚴密之數學證明其複雜度為0 (Log d )，在此，d 是在圖形上，對任兩頂點之距離求其極大值，而所謂兩點之距離是以最長路徑之邊數計算。一般而言d 小於n ，尤其在稀疏的圖形上，d 可能遠小於n ，最差的情況下d 才等於n-1。