上頁　1│2│3│4│5│6│7　次頁

未來數學家的挑戰
計算量問題 （第 2 頁）

楊照崑;楊重駿

 

首頁 | 搜尋

．原載於數學傳播十卷二期
．作者當時任教於美國佛羅里大學統計系;美國海軍研究實驗所

•註釋
•對外搜尋關鍵字
 
二、計算量

計算量，顧名思意，是指解決某問題所需要計算的時間，但因每個複雜問題的計算往往都要經過許多不同的運算，除加減乘除四則外，還要包含比較，取數據，存數據等等，若仔細計算起來，十分困難，一般都只繪出一兩個主要的量，加以統計，以上節中售貨員旅行問題為例，其主要的工作是對每一個排法加起總路徑之長，因對 n 城而言，有 (n-1)! 的排法，我們就定其計算量為 O(n!)，即在 n! 之層次（order 即 O 縮寫之來源）之內。

舉二個例子，我們若要求 n 個數的和或平均值，則其計算量為 O(n)。 但若我們要把 n 個數字依次排列，則其計算量會因做法的不同而有相當的差別，一個直接了當的方法是，先求出最大的（比 (n-1) 次），再從不是最大的中間求次大的（比 (n-2) 次），再求第三大的（比 (n-3) 次），……如此一共比了

\begin{displaymath} (n-1)+(n-2)+\cdots+1\\ =\frac{n(n-1)}{2}\\ \end{displaymath}

次就可以完成此工作。因此我們以 O(n2)，即在 n2 之層次來表此方法的計算量。 另外一種快排法，先把 n 個數分成若干小塊，每塊排好之後再合起來， 則可以證明此種方法之計算量為 $O(n{\log_2{n}})$ 1 ，因排數字與排名字，電話號碼相同，這種排法很有實用價值， 例如某大城有一百萬戶，則 n2=1012，而 $n{\log_2n}$ 只有 2 x 107，其差別三個月與一分鐘之比。

一般計算量的層次多以下表來區分，

\begin{eqnarray*} &&O(\log n)<O(n)<O(n\log_2n)<O(n^2)\\ &&<O(n^k)<O(2^n)<O(k^n)<O(n!) \end{eqnarray*}


在上表中，k 為某一大於 2 的正整數，它們中間都有一道鴻溝，有基本層之不同，在計算機理論上，若某人能發現一個新的方法，降低一個層次的計算量，那麼他的新方法有資格稱之為一個突破，可以不朽矣。表1 有一個對上項各量之比較，是以計算機每秒作一百萬次 (106) 計算為原則。

n $\log n$ n $n\log n$ n2 n3 2n 3n n!
10 10-6 10-5 10-5 10-4 10-3 10-3 0.059 0.45
20 10-6 10-5 10-5 10-4 10-2 1(秒) 58(分) 1年
50 10-5 10-4 10-4 0.0025 0.125 36年 2 x 1010年 1057年
1000 10-5 10-3 10-3 1 16小時 10333年 極大 極大
106 10-5 1 6 1月 105年 極大 極大 極大
109 10-5 16小時 6天 3年 3 x 109年 極大 極大 極大
表一：以計算機每秒做一百萬次時完成各層次計算量所約需的時間（若無單位，均以秒為單位）

在這個表中，特別注意 n3 與 2n 中之差異，一般稱 2n 為計算量呈指數上升，而 n3 或 nk 之計算量呈 n 的方次上升 2 ， 對目前及未來的計算機而言，一個呈方次上升的計算量應可以應付，但對一個呈指數上升的計算量在 n 相當大時則毫無希望。 因此計算機學家所集中精力的方向在如何將一個呈指數上升的計算量問題，簡化成一個方次上升的計算量問題。 我們定義凡對一個問題中最重要的參數 n 而言，若能找到一個方法可以以方次上升的計算量完成， 我們稱此問題為一 P-問題（P 為英文多項式 Polynomial 之第一字母），包含所有此類問題之集合以 P 表示之。

   

上頁　1│2│3│4│5│6│7　次頁

 回頁首
 
（若有指正、疑問……，可以在此 留言 或 寫信 給我們。）
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯：王昱昇 ／ 校對：陳文是 ／ 繪圖：簡立欣 最後修改日期：6/29/2002