?算法的漸進分析（asymptotic algorithm analysis）簡稱算法分析。算法分析直接與它所求解的問題的規模 n 有關，因此，通常將問題規模作為分析的參數，求算法的時間和空間開銷與問題規模的關系。

漸進的時間復雜度

?計算程序步數的目的是想比較兩個或多個完成相同功能的程序的時間復雜度，并估計當問題規模變化時，程序的運行時間如何隨之變化。
?要確定一個程序的準確的程序步數是非常困難的，而且也不是很必要。因為程序步數這個概念本身不是一個精確的概念。例如，賦值語句 x=a 和 x=a+b*(c-d)-e/f 居然具有相同的程序步數。
?由于程序步數不能確切的反映運行時間，所以用精確的程序步數來比較兩個程序，其結果不一定有價值。前面討論迭代求和程序與遞歸求和程序的程序步數時，程序步數為 3n+2 的程序反而比程序步數為 3n+4 的程序運行時間多。但是，當兩個程序的程序步數相差很大時，例如一個是 $?{\log }_2(n+1)?$,另一個是 $n?(n?1)/2$ 時，明顯后者比前者運行時間多。
?因此，如果精確計算有困難，我們只要能夠得出一個是 ${\log }_{2}n$的數量級，一個是 $n^2$的數量級，后者比前者運行時間多的結論，也能達到分析的目的。

大 $O$ 漸進表示

? 要全面分析一個算法，需要考慮算法在最壞情況下的時間代價，在最后情況下的時間代價，在平均情況下的時間代價。對于最壞情況，主要采用大 $O$ 表示法來描述。
? 大 $O$ 表示法的一般前提是：當且僅當存在正整數 $c$ 和 $n_0$,使得 $T(n)\le cf(n)$，使得所有的 $n\ge n_0$ 成立，則稱該算法的時間增長率在 $O(f(n))$ 中，記為 $T(n)=O(f(n))$ 。
? 使用大 $O$ 表示法時需要考慮關鍵操作的程序步數。如果最后需要給出的時漸進值，可直接考慮關鍵操作的程序步數，找出其與 $n$ 的函數關系 $f(n)$ ，從而得到漸進時間復雜度。

接下來，根據大 $O$ 表示法來看看接下來的例子。
1、（線性函數）考察 $T(n)=3n+2$。
$$T(n)=O(n)$$
2、（平方函數）考察 $T(n)=10n^2+4n+2$
$$T(n)=O(n^2)$$
3、（指數函數）考察 $T(n)=6?2^n+n^2$
$$T(n)=O(2^n)$$
4、（常數函數）考察 $T(n)=9$
$$T(n)=O(1)$$

為了更好在具體情況下使用大 $O$ 表示法，我們需要知道大 $O$ 表示法的幾個規則。

1、加法規則： 當兩個并列的的程序段的時間代價分別為為 $T_1(n)=O(f(n))$ 和 $T_2(m)=O(g(m))$ 時，那么將兩個程序段連在一起后整個程序段的時間代價為
$$T(n,m)=T_1(n)+T_2(m)=O(\max \{f(n),g(m)\})$$
所謂 $\max \{f(n),g(m)\}$ 是指當 $n$ 和 $m$ 充分大時取 $f(n)$ 與 $g(m)$ 中的最大值。在這個意義下顯然有如下關系：
$$c<{\log }_{2}n<n<n{\log }_{2}n<n^2<n^3<2^n<3^n<n!$$

示例如下

//程序 1.26 計算漸進時間復雜度的程序示例 void example(float x[][n],int m){float sum[m];int i,j;for(i=0;i<m;i++){sum[i]=0.0;for(j=0;j<n;j++)sum[i]+=x[i][j]; //計算第 i 行的元素和}for(i=0;i<m;i++)cout<<"Line"<<i<<":"<<sum[i]<<endl; //打印第 i 行的累加和 }

根據加法規則，該程序的漸進時間復雜度為 $O(\max \{m\times n,m\})$ 。

2、乘法規則： 如果存在多層的嵌套循環，關鍵操作應在最內層循環中。先自外向內層層分析每層循環的漸進時間復雜度，然后利用大 $O$ 表示法來計算其漸進時間復雜度。也就是說，當兩個嵌套的程序段的時間代價分別是 $T_1(n)=O(f(n))$ 和 $T_2(m)=O(g(m))$ 時，那么整個時間段的時間代價為
$$T(n,m)=T_1(n)\times T_2(m)=O(f(n)\times g(m))$$

總結

以上是生活随笔為你收集整理的【数据结构】算法的渐进分析-渐进时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。