我們先給出推導(dǎo)的方法，然后下面一步一步來推導(dǎo)。

推導(dǎo)大O階

用常數(shù)1取代運行時間中的所有加法常數(shù)

在修改后的運行次數(shù)函數(shù)中，只保留最高階項

如果最高階存在且不是1，則去除這個項相乘的常數(shù)

所得結(jié)果即為大O階

示例

int sum = 0，n = 100; //以分號結(jié)尾，代碼執(zhí)行一次 sum = (1+n)*n/2 //執(zhí)行一次 cont<<sum<<endl; //執(zhí)行一次

運行次數(shù)為3，而在上面推導(dǎo)的推導(dǎo)大O階方法中我們說了，用1代碼所有的加法，什么意思呢？我們的3是經(jīng)過1+1+1算出來的，我們用1代替所有的加法。而這個表達式只有1，沒有最高階項，所以結(jié)果1即為大O階。我們把具有O（1）的時間復(fù)雜度的叫做常數(shù)階。

int i; for(i = 0;i<n;i++) {/*其他常數(shù)階程序代碼*/ }

我們可以發(fā)現(xiàn)，花括號里的就是常數(shù)階，而for循環(huán)循環(huán)了n次，也就是說，做了n+常數(shù)階次執(zhí)行次數(shù)，根據(jù)上面推導(dǎo)大O階方法，我們找到了最高階項n，舍棄后面常數(shù)項，所以我們的時間復(fù)雜度為O(n)，我們把這類情況稱為線性階。

順便一提，一般來說，我們分析算法的時間復(fù)雜度，關(guān)鍵就是分析循環(huán)結(jié)構(gòu)的運行情況。

int count = 1; while(count < n) {count = count * 2;/*其他常數(shù)階程序代碼*/ }

從這里的代碼我們可以看出，退出循環(huán)的條件是count<n，而count是通過自身乘2來更新自我然后跳出循環(huán)的。也就是說，設(shè)count更新次數(shù)為x，其可以寫出$2^x=n$的式子，而我們大O(n)里面的n實際上指的是這里的x，根據(jù)高中數(shù)學所學的指對互換，我們可以寫出$x=lo{g}_{2}n$。所以這個循環(huán)的時間復(fù)雜度為O(logn)，我們把這類情況叫做對數(shù)階。

int i ,j ; for (i - 0; i < n; i++) {for ( j - 0 ; j < n ; j++ ){/*時間復(fù)雜度為O(1)的程序步驟序列*/} }

對于這種就不必多說了，時間復(fù)雜度為O$(n^2)$。我們把這類情況叫做平方階。

說完上面所有的情況了，現(xiàn)在我們來幾個題來練手。

x = 0;y = 0; for(int k = 0;k<n;k++){x++; } for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){y++;} }

分析算法，根據(jù)推導(dǎo)大O階方法，第一行執(zhí)行1次，第一個循環(huán)執(zhí)行n次，第一個內(nèi)嵌循環(huán)外層n次，內(nèi)層n次，也就是n的平方。把常數(shù)變?yōu)?，然后抓大頭，最高項系數(shù)為1，那么只剩下$n^2$。所以該代碼的時間復(fù)雜度為O$(n^2)$，從完整的代碼分析下來我們也可以發(fā)現(xiàn)，實際上我們只需要找最復(fù)雜的那個循環(huán)開始分析就可以了，因為其他的代碼所含的時間復(fù)雜度最終根據(jù)推導(dǎo)大O階方法都會被省略。下面看一個比較難的例子。

void exam(fload x[][],int m,int n) {float sum[];for(int i = 0;i<m;i++){sum[i] = 0.0;for(int j = 0;j<n;j++){sum[i]+=x[i][j];}}for(i = 0;i<m;i++)cout<<i<<":"<<sum[i]<<endl; }

最復(fù)雜的就是中間的內(nèi)嵌循環(huán)，外層循環(huán)為從0到m，內(nèi)層循環(huán)0到n，所以該時間復(fù)雜度應(yīng)為O(m+n)。

for(i = 1;i<=n;i++)for(j = 1;j<=n;j++){c[i][j]=0;for(k = 1;k<=n;k++)c[i][j] = c[i][j]+a[i][k]*b[k][j];}

上面這個是一個N×N矩陣相乘的算法，連續(xù)三層循環(huán)，第一次執(zhí)行次數(shù)為n，第二層執(zhí)行次數(shù)也為n，第三層執(zhí)行次數(shù)還是n。所以該題算法復(fù)雜度為O$(n^3)$。

for(i = 1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x = x+1；

這里最外層執(zhí)行次數(shù)n，但是最外層執(zhí)行1次，第二層就循環(huán)1次；最外層執(zhí)行第2次，第二層循環(huán)兩次；根據(jù)等差數(shù)列求和公式，即第二層有1+2+3+…+n，即$\frac{n(1+n)}{2}$次。當然第三層就不好理解了，所以我們接下來換一種方法。

對于三層循環(huán)問題，我們還是直接列出最外層的前幾項比較好。在i = 1的時候，內(nèi)層循環(huán)全部加起來只循環(huán)一次。在i = 2的時候，第二層循環(huán)啟動兩次循環(huán)，所以總共執(zhí)行1+2，對于i = 3，第二層啟動三次循環(huán)，第三層也是三次循環(huán)。也就是說總共執(zhí)行1+2+3。如果聽不太懂，我們可以用圖來表示，即：

所以實際上以上規(guī)律是由n來控制的，從上面的圖來看的話，根據(jù)我們所得規(guī)律，i=1里面有一個$\frac{i(1+i)}{2}$，i = 2里面也有一個$\frac{i(1+i)}{2}$，以此類推我們可以寫出下面的式子：${\sum }_{i=1}^n\frac{i(i+1)}{2}$。

我們化簡一下上面的式子：${\sum }_{i=1}^n(\frac{i^2}{2}+\frac{i}{2})=\frac{1}{2}{\sum }_{i=1}^n(i^2?i)$。

這里用等差求和公式帶入求解，即可得出答案$\frac{n(n+1)(n+2)}{6}$，根據(jù)我們前面說的大O階推導(dǎo)，可以得出本題的時間復(fù)雜度為$n^3$。

總結(jié)

以上是生活随笔為你收集整理的数据结构杂谈番外篇——时间复杂度计算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。