算法(algorithm )是指令的集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。它是明確定義的可計(jì)算過(guò)程，以一個(gè)數(shù)據(jù)集合作為輸入，并產(chǎn)生一個(gè)數(shù)據(jù)集合作為輸出。一個(gè)算法通常來(lái)說(shuō)具有以下五個(gè)特性：

• 輸入：一個(gè)算法應(yīng)以待解決的問(wèn)題的信息作為輸入。
• 輸出：輸入對(duì)應(yīng)指令集處理后得到的信息。
• 可行性：算法是可行的，即算法中的每一條指令都是可以實(shí)現(xiàn)的，均能在有限的時(shí)間內(nèi)完成。
• 有窮性：算法執(zhí)行的指令個(gè)數(shù)是有限的，每個(gè)指令又是在有限時(shí)間內(nèi)完成的，因此整個(gè)算法也是在有限時(shí)間內(nèi)可以結(jié)束的。
• 確定性：算法對(duì)于特定的合法輸入，其對(duì)應(yīng)的輸出是唯一的。即當(dāng)算法從一個(gè)特定輸入開(kāi)始，多次執(zhí)行同一指令集結(jié)果總是相同的。

簡(jiǎn)單的說(shuō)，算法就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫(xiě)程序，都是在實(shí)施某種算法。前者是算法的邏輯形式，后者是算法的代碼形式。舉例：如何求0+1+2+3+...10000=?

• 算法1：依次相加? while do-while ?for

• 算法2：高斯解法：首尾相加*50? ? (1+10000)*10000/2 ?? 100*101/2

• 算法3：使用遞歸實(shí)現(xiàn)：sum(100) = sum(99)+100? ?sum(99)= sum(98)+99 ..... ? sum(2) = sum(1)+2 ? sum(1) = 1

評(píng)價(jià)算法優(yōu)劣的依據(jù)：復(fù)雜度(時(shí)間復(fù)雜度和空間復(fù)雜度)

算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時(shí)的計(jì)算機(jī)所需資源的多少上，計(jì)算機(jī)資源最重要的是時(shí)間和空間資源，因此復(fù)雜度分為時(shí)間和空間復(fù)雜度

時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；

空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

時(shí)間復(fù)雜度(Time Complexity))定義

時(shí)間頻度：

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試。一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度，表示為T(mén)(n)，n表示問(wèn)題的規(guī)模時(shí)間復(fù)雜度：

但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律，想知道問(wèn)題的規(guī)模，而不是具體的次數(shù)，此時(shí)引入時(shí)間復(fù)雜度。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，

若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱(chēng)O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。T(n)=O(f(n))或者說(shuō)：時(shí)間復(fù)雜度就是時(shí)間頻度去掉低階項(xiàng)和首項(xiàng)常數(shù)。注意：時(shí)間頻度與時(shí)間復(fù)雜度是不同的，時(shí)間頻度不同但時(shí)間復(fù)雜度可能相同。比如：某兩個(gè)算法的時(shí)間頻度是?

T(n) = 100000n2+10n+6 ???

T(n) = 10n2+10n+6 ? T(n) = n2? ??

但是時(shí)間復(fù)雜度都是 T(n) = O(n2)最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度：

最壞情況下的時(shí)間復(fù)雜度稱(chēng)最壞時(shí)間復(fù)雜度。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。?

這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。

在最壞情況下的時(shí)間復(fù)雜度為T(mén)(n)=O(n)，它表示對(duì)于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于O(n)。?

平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。鑒于平均復(fù)雜度

第一，難計(jì)算

第二，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的。

所以一般討論最壞時(shí)間復(fù)雜度

比如 我要求你在字典里查同一個(gè)字，告訴我這個(gè)字在字典的那一頁(yè)。如果一頁(yè)一頁(yè)的翻，你需要多少時(shí)間呢？

最優(yōu)的情況就是這個(gè)字在第一頁(yè)，

最壞的情況就是這個(gè)字是 整本字典的最后一個(gè)字。

所以即使我故意為難你，你也不會(huì)花費(fèi)比找整本字典最后一個(gè)字還長(zhǎng)的時(shí)間。

當(dāng)然，此時(shí)聰明的你就會(huì)想用部首、筆畫(huà)等去查，才不要傻乎乎的一頁(yè)一頁(yè)翻，此時(shí)的你就會(huì)擇優(yōu)選擇，因?yàn)榇藭r(shí)你最壞的情況就是我給你部首筆畫(huà)最多、除部首外筆畫(huà)最多的一個(gè)超級(jí)復(fù)雜的一個(gè)字，但顯然比翻整本字典快得多。

為了進(jìn)一步說(shuō)明算法的時(shí)間復(fù)雜度，我們定義 Ο、Ω、Θ符號(hào)。

Ο(歐米可榮)符號(hào)給出了算法時(shí)間復(fù)雜度的上界(最壞情況? <=)，比如T(n) =O(n2)

Ω(歐米伽)符號(hào)給出了時(shí)間復(fù)雜度的下界(最好情況 >=)，比如T(n) =Ω(n2)

而Θ(西塔)給出了算法時(shí)間復(fù)雜度的精確階(最好和最壞是同一個(gè)階? =)，比如T(n) =Θ(n2)

時(shí)間復(fù)雜度計(jì)算：

根本沒(méi)有必要計(jì)算時(shí)間頻度，即使計(jì)算處理還要忽略常量、低次冪和最高次冪的系數(shù)，所以可以采用如下簡(jiǎn)單方法：

• 找出算法中的基本語(yǔ)句；

算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。

• 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；

• 只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，

• 可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。

• 用大Ο記號(hào)表示算法的時(shí)間性能。

• 將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。

時(shí)間復(fù)雜度舉例：

• 一個(gè)簡(jiǎn)單語(yǔ)句的時(shí)間復(fù)雜度為O(1)。

int count=0;

• 100個(gè)簡(jiǎn)單語(yǔ)句的時(shí)間復(fù)雜度也為O(1)。(100是常數(shù)，不是趨向無(wú)窮大的n)

int count=0;

• 一個(gè)循環(huán)的時(shí)間復(fù)雜度為O(n)。

int n=8, count=0;for (int i=1; i<=n; i++) count++;T(n)=O(n)

• 時(shí)間復(fù)雜度為O(log2 n)的循環(huán)語(yǔ)句。?

int n=8, count=0;for (int i=1; i<=n; i*=2) count++;1? 2? 4? ?8? 16? 32??230=1024*1024*1024 = 1000*1000*1000=10億

• 時(shí)間復(fù)雜度為O(n2)的二重循環(huán)。

int n=8, count=0;for (int i=1; i<=100n; i++) for (int j=1; j<=10n; j++) count++;

• 時(shí)間復(fù)雜度為O(nlog2n)的二重循環(huán)。

int n=8, count=0;for (int i=1; i<=n; i*=2) for (int j=1; j<=n; j++) count++;?

• 時(shí)間復(fù)雜度為O(n2)的二重循環(huán)。

int n=8, count=0;for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) count++;1+2+3+4....+n=(1+n)*n/2需要復(fù)雜些數(shù)學(xué)運(yùn)算：1+2+3+.....+n=(n+1)*n/2 ?時(shí)間復(fù)雜度是 O(n2)后面講解查找和排序算法時(shí)會(huì)大量的設(shè)計(jì)時(shí)間復(fù)雜度，作為選擇查找和排序算法的重要依據(jù)常用的時(shí)間復(fù)雜度級(jí)別：

• 常數(shù)階O(1)?

• 對(duì)數(shù)階O(log2n)

• 線性階O(n)

• 線性對(duì)數(shù)階O(n*log2n)

• 平方階O(n2)?

• 立方階O(n3)

• ...

• k次方階O(nk)

• 指數(shù)階O(2n)

• 階乘階O(n!)

上面各種時(shí)間復(fù)雜度級(jí)別，執(zhí)行效率越來(lái)越低。

大家發(fā)現(xiàn)對(duì)數(shù)階O(log2n)和線性階O(n)的效率差異了嗎，當(dāng)n=10的8次方(1億)時(shí)，執(zhí)行此時(shí)一個(gè)是1億次，一個(gè)是8次。

所以編寫(xiě)算法時(shí)一定要注意時(shí)間復(fù)雜度的選擇。

空間復(fù)雜度(Space Complexity))：

算法的存儲(chǔ)量包括:?

• 程序本身所占空間

• 輸入數(shù)據(jù)所占空間；

• 輔助變量所占空間

輸入數(shù)據(jù)所占空間只取決于問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間大小的量度，一般也作為問(wèn)題規(guī)模n的函數(shù)，以數(shù)量級(jí)形式給出，記作：S(n) = O(g(n))

• 空間復(fù)雜度分析1：

int?fun(int?n){???int?i，j，k，s;?????s=0;????for?(i=0;i<=n;i++)??????????????????for?(j=0;j<=i;j++)???????????????for?(k=0;k<=j;k++)???????????????????s++;?????return(s);}由于算法中臨時(shí)變量的個(gè)數(shù)與問(wèn)題規(guī)模n無(wú)關(guān)，所以空間復(fù)雜度均為S(n)=O(1)。

• 空間復(fù)雜度分析2：

void?fun(int?a[]，int?n，int?k)?{ //數(shù)組a共有n個(gè)元素 int?i; if?(k==n-1) ???for?(i=0;i ???printf(“%d\n”，a[i]);??//執(zhí)行n次??else {?? ??for?(i=k;i a[i]=a[i]+i*i;　　//執(zhí)行n-k次??????fun(a，n，k+1); }}?此屬于遞歸算法(后續(xù)講解)，每次調(diào)用本身都要分配空間，fun(a,n,0)的空間復(fù)雜度為O(n)。

注意：

• 空間復(fù)雜度相比時(shí)間復(fù)雜度分析要少

• 對(duì)于遞歸算法來(lái)說(shuō)，代碼一般都比較簡(jiǎn)短，算法本身所占用的存儲(chǔ)空間較少，但運(yùn)行時(shí)需要占用較多的臨時(shí)工作單元；

• 若寫(xiě)成非遞歸算法，代碼一般可能比較長(zhǎng)，算法本身占用的存儲(chǔ)空間較多，但運(yùn)行時(shí)將可能需要較少的存儲(chǔ)單元。

總結(jié)

以上是生活随笔為你收集整理的一个算法对于某个输入的循环次数是可以事先估计出来的_数据结构与算法：算法...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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