Matlab 導引：複雜度

Matlab 的指令 clock 輸出 1 乘 6 的序列， 其數值依序代表：年 (西元)、月、日、時、分、秒。 前五個是正整數，但秒是浮點數。可以用 round(clock) 取得全是整數值的答案。 答案的準確性由您所用的電腦負責，因為 Matlab 是從作業系統那裡取得這些資料。 另外還有兩個指令來開始和結束碼表：

tic

將碼表歸零並開始計時。

toc

停止碼表，並輸出以秒為單位的時間。

>> A=rand(100,100);
>> tic; B=inv(A); det(A)*det(B), toc
ans =
    1.0000
elapsed_time =
    0.1100

另一個指令 cputime 輸出自從這一次執行 Matlab 以來， 總共使用了多少秒的 CPU 時間。例如 round(cputime/60) 會知道您這回從開始使用 Matlab 到目前為止，共用了大約幾分鐘的 CPU 時間。 我們也可以用它來測量一套指令共使用了多少 CPU 時間：

>> t=cputime; B=inv(A); det(A)*det(B), cputime-t ans = 1.0000 elapsed_time = 0.0900

在微軟視窗環境的個人電腦上，CPU 時間和碼表計時的結果相差不會太大， 但是在多人多工的計算環境內，就可能有相當的出入。

用時間來估計一套指令的執行複雜度，未必是有意義的。 因為每台電腦的執行效率不同。 數學家更關心的是計算步驟數。 Matlab 內建一個計數器，記得加減乘除、次方這些基本計算步驟的次數。 指令 flops 顯示此計數器的值，而 flops(0) 將其歸零。例如

>> flops(0); 2+(3-4*5)/6; flops ans = 4

有一些簡單的基本函數的計算步驟被忽略，例如 exp(2.5) 和 sin(2.5) 的計算步驟根本不計，而 sqrt(2.5) 被計一次。 有些計算步驟會取近似值，例如 sum(1:10) 明明只有 9 次加法， 但是 Matlab 算它 10 次。也就是說 sum(1:n) 就當有 n 次計算。 當 n 很大的時候，也就差不多了。例如

>> A=rand(10,10); x = rand(10,1); >> flops(0); x'*x; flops ans = 20 >> flops(0); A*x; flops ans = 200

利用 flops 可以很方便地估計某個計算程式的複雜度 (complexity)。 通常我們假設，當輸入矩陣的維度是 N 乘 N 的時候， 一個矩陣計算的複雜度是 O(N ^p)， 或者說計算次數大約是

以下我們示範一套實驗步驟， 用以估計 Matlab 的 inv (反矩陣) 程式之計算複雜度。 我們分別以 N=10、20、40、80 的亂數方陣做反矩陣， 並將它們的計算次數記錄在 f 序列中。

>> N=[10 20 40 80]; >> for k=1:4, A=rand(N(k),N(k)); flops(0); inv(A); f(k)=flops; end; >> f f = 2601 18186 136364 1056506

光是從 f 的值，不方便看出端倪。因為實驗中的 N 以 2 的倍數成長， 根據複雜度的假設，f 的值大約是

>> log2(f(2:4) ./ f(1:3))
ans =
    2.8057    2.9066    2.9538

>> f ./ N.^3
ans =
    2.6010    2.2732    2.1307    2.0635

[ 上一單元 ]    [ 下一單元 ]    [ 上層目錄 ]