1.3 知識拓展

算法時間復雜度分析是評估算法優劣的一個重要指標，同時算法時間復雜度分析和執行時間的測試也是一個學習難點。本節在1. 2節的基礎上拓展介紹相關分析和計算的技巧。

1.3.1 算法時間復雜度分析

分析算法時間復雜度的一般步驟如圖1-15所示。

根據循環統計基本語句的執行次數這種算法時間復雜度的分析方法已在1.1.3節中進行了介紹。對于一個遞歸算法又該如何分析時間復雜度呢？

遞歸算法的分析方法比較多，常用的是迭代法。迭代法的基本步驟是先將遞歸算法簡化為對應的遞歸方程，然后通過反復迭代，將遞歸方程的右端變換成一個級數，最后求級數的和，再估計和的漸進階。

【例1-1】遞歸求n！的算法如下，試分析其算法時間復雜度。

分析：

算法的遞歸方程為T（n）=T（n-1）+O（1）

迭代展開：

因此，該遞歸算法的時間復雜性是線性的。

說明：遞歸方程的計算除了迭代法之外，還有代換法、遞歸樹法、主定理法等，讀者可閱讀相關參考書籍進一步了解。

【例1-2】計算下列程序段的時間復雜度。

分析：

循環語句while（s＜n） s+= ++i；

等價于while（s＜n）{i=i+1；s+=i；}

顯然i每次增加1，循環體就執行一次，執行過程如下：

因此，滿足1+2+3+4+…+（x+1）≥n的最小x值即為循環體執行的次數。顯然此時x是數量級的，因此時間復雜度是。

【例1-3】計算下列程序段的時間復雜度。

分析：

觀察i的變化規律：3¹，3²，3³，3⁴…

設循環體共執行x次，則：3^x≤n，解得：x≤log₃n。

說明x從1到log₃n共執行了log₃n次，因此該程序段的時間復雜度為O（log₃n）。

【例1-4】假設n是3的倍數，計算下列程序段的時間復雜度。

分析：

基本語句y+=i*j；的執行次數為（n-3*i+1）=（n-2）+（n-5）+…+4+1=，因此，這段代碼的時間復雜度為O（n²）。

【例1-5】計算下列程序段的時間復雜度。

分析：

該程序段是雙重循環，著重考慮雙重循環內循環體基本語句s=s+a[i][j]；執行的次數。

觀察外層循環變量i的變化規律：2¹，2²，2³，2⁴，…參照例1-3的方法，可知外層循環執行了log₂n次；再考察外層循環變量j的變化規律：1，2，3，4，…共執行了n次。基本語句s=s+a[i][j]；執行的次數=外層循環執行次數×內層循環執行次數=nlog₂n。

因此，該程序段的時間復雜度為O（nlog₂n）。

1.3.2 算法執行時間測試

1.1.3節中介紹了利用漸進時間復雜度這種事前分析估算的方法來分析算法的效率。本節將介紹利用后期測試法來分析算法效率。

不同算法用計算機程序實現后，其執行時間也不盡相同。算法執行時間的精確測試對算法執行效率的分析和評價也有著重要的意義。

測試算法執行時間的常規方法如下：在待測試的算法代碼片段前，創建一個變量記錄當前的系統時間；待算法代碼片段執行完成后，用另一個變量記錄新的時間；二者之差即為算法代碼片段的執行時間。算法執行時間的測試流程如圖1-16所示。

實例代碼如下：

說明：CLOCKS_PER_SEC是time. h頭文件中宏定義的一個常數，用于將clock（）函數的結果轉化為以秒為單位的量。

目前的PC操作系統都是支持多任務的，操作系統分配時間片（Time slice）給每個任務輪流使用CPU。在多任務操作系統下，使用本節介紹的常規時間測試方法檢測算法代碼片段執行時間所得的結果為算法在計算機上的運行時間，而不是算法在CPU的執行時間，測得的時間比算法實際的執行時間大，并不是精確的結果。不過，這種常規測試方法用于在同一計算機環境下對多個算法進行時間性能比較還是可行的。