2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

算法時(shí)間復(fù)雜度定義

算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n)=O(f(n))。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。

一般情況下，隨著n的增大，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法。

O(1)叫常數(shù)階、O(n)叫線性階、O(n^2)叫平方階。

推導(dǎo)大O階：

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

2．在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

3．如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

常數(shù)階

int sum = 0,n = 100; /* 執(zhí)行一次 */ sum = (1 + n) * n / 2; /* 執(zhí)行一次 */ printf("%d", sum); /* 執(zhí)行一次 */

運(yùn)行次數(shù)函數(shù)是f(n)=3,時(shí)間復(fù)雜度為O(1)。與問題的大小無關(guān)（n的多少），執(zhí)行時(shí)間恒定的算法，叫常數(shù)階。

線性階

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

時(shí)間復(fù)雜度為O(n)，因?yàn)檠h(huán)體中的代碼須要執(zhí)行n次。

對(duì)數(shù)階

int count = 1; while (count < n) {count = count * 2;/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */ }

由2x=n得到x=log2n,時(shí)間復(fù)雜度為O(logn)。

平方階

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

外層的循環(huán)時(shí)間復(fù)雜度O(n)，內(nèi)層時(shí)間復(fù)雜度為O(n)，所以這段代碼的時(shí)間復(fù)雜度為O(n^2)。

n++; /* 執(zhí)行次數(shù)為1 */ function(n); /* 執(zhí)行次數(shù)為n */ int i, j; for (i = 0; i < n; i++) /* 執(zhí)行次數(shù)為n^2 */ {function (i); } for (i = 0; i < n; i++) /* 執(zhí)行次數(shù)為n(n + 1)/2 */ {for (j = i; j < n; j++){/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */} }

執(zhí)行次數(shù)f(n)=1+n+n^2+n(n+1)/2=3/2·n^2+3/2·n+1，時(shí)間復(fù)雜度也是O(n2)。

歡迎掃描下方二維碼，持續(xù)關(guān)注：

互聯(lián)網(wǎng)工程師（id:phpstcn），我們一起學(xué)習(xí)，一起進(jìn)步

轉(zhuǎn)載于:https://my.oschina.net/xushuhui/blog/3040214

總結(jié)

以上是生活随笔為你收集整理的《大话数据结构》读后总结（六）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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