⑴ 分析演算法時間復雜度
什麼演算法？？
⑵ 演算法時間復雜度是指什麼
演算法的時間復雜度是一個函數，它定性描述該演算法的運行時間。
這是一個代表演算法輸入值的字元串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。
演算法的時間復雜度取決於什麼
演算法的時間復雜度取決於待處理數據的狀態以及問題的規模。演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
⑶ 演算法的空間復雜度和時間復雜度的關系
論壇
活動
招聘
專題
打開CSDN APP
Copyright © 1999-2020, CSDN.NET, All Rights Reserved
搜索博文/帖子/用戶
登錄
zolalad
關注
演算法的時間復雜度和空間復雜度-總結 原創
2013-09-20 16:01:26
308點贊
zolalad
碼齡9年
關注
演算法的時間復雜度和空間復雜度-總結
通常，對於一個給定的演算法，我們要做 兩項分析。第一是從數學上證明演算法的正確性，這一步主要用到形式化證明的方法及相關推理模式，如循環不變式、數學歸納法等。而在證明演算法是正確的基礎上，第二部就是分析演算法的時間復雜度。演算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出演算法的優劣與否。因此，作為程序員，掌握基本的演算法時間復雜度分析方法是很有必要的。
演算法執行時間需通過依據該演算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執行時間通常有兩種方法。
一、事後統計的方法
這種方法可行，但不是一個好的方法。該方法有兩個缺陷：一是要想對設計的演算法的運行性能進行評測，必須先依據演算法編制相應的程序並實際運行；二是所得時間的統計量依賴於計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優勢。
二、事前分析估算的方法
因事後統計方法更多的依賴於計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優劣。因此人們常常採用事前分析估算的方法。
在編寫程序前，依據統計方法對演算法進行估算。一個用高級語言編寫的程序在計算機上運行時所消耗的時間取決於下列因素：
(1). 演算法採用的策略、方法；(2). 編譯產生的代碼質量；(3). 問題的輸入規模；(4). 機器執行指令的速度。
一個演算法是由控制結構（順序、分支和循環3種）和原操作（指固有數據類型的操作）構成的，則演算法時間取決於兩者的綜合效果。為了便於比較同一個問題的不同演算法，通常的做法是，從演算法中選取一種對於所研究的問題（或演算法類型）來說是基本操作的原操作，以該基本操作的重復執行的次數作為演算法的時間量度。
1、時間復雜度
（1）時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
（2）時間復雜度 在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。 一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
另外，上面公式中用到的 Landau符號其實是由德國數論學家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數論》首先引入，由另一位德國數論學家艾德蒙·朗道（Edmund Landau）推廣。Landau符號的作用在於用簡單的函數來描述復雜函數行為，給出一個上或下（確）界。在計算演算法復雜度時一般只用到大O符號，Landau符號體系中的小o符號、Θ符號等等比較不常用。這里的O，最初是用大寫希臘字母，但現在都用大寫英語字母O；小o符號也是用小寫英語字母o，Θ符號則維持大寫希臘字母Θ。
T (n) = Ο(f (n)) 表示存在一個常數C，使得在當n趨於正無窮時總有 T (n) ≤ C * f(n)。簡單來說，就是T(n)在n趨於正無窮時最大也就跟f(n)差不多大。也就是說當n趨於正無窮時T (n)的上界是C * f(n)。其雖然對f(n)沒有規定，但是一般都是取盡可能簡單的函數。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示就可以了。注意到大O符號里隱藏著一個常數C，所以f(n)里一般不加系數。如果把T(n)當做一棵樹，那麼O(f(n))所表達的就是樹干，只關心其中的主幹，其他的細枝末節全都拋棄不管。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。 按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。
從圖中可見，我們應該盡可能選用多項式階O(nk)的演算法，而不希望用指數階的演算法。
常見的演算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
一般情況下，對一個問題（或一類演算法）只需選擇一種基本操作來討論演算法的時間復雜度即可，有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦予不同的權值，以反映執行不同操作所需的相對時間，這種做法便於綜合比較解決同一問題的兩種完全不同的演算法。
（3）求解演算法的時間復雜度的具體步驟是：
⑴ 找出演算法中的基本語句；
演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。
⑵ 計算基本語句的執行次數的數量級；
只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。
⑶ 用大Ο記號表示演算法的時間性能。
將基本語句執行次數的數量級放入大Ο記號中。
如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。
Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者（即多項式時間復雜度的演算法）是有效演算法，把這類問題稱為P（Polynomial,多項式）類問題，而把後者（即指數時間復雜度的演算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。
一般來說多項式級的復雜度是可以接受的，很多問題都有多項式級的解——也就是說，這樣的問題，對於一個規模是n的輸入，在n^k的時間內得到結果，稱為P問題。有些問題要復雜些，沒有多項式時間的解，但是可以在多項式時間里驗證某個猜測是不是正確。比如問4294967297是不是質數？如果要直接入手的話，那麼要把小於4294967297的平方根的所有素數都拿出來，看看能不能整除。還好歐拉告訴我們，這個數等於641和6700417的乘積，不是素數，很好驗證的，順便麻煩轉告費馬他的猜想不成立。大數分解、Hamilton迴路之類的問題，都是可以多項式時間內驗證一個「解」是否正確，這類問題叫做NP問題。
（4）在計算演算法時間復雜度時有以下幾個簡單的程序分析法則:
(1).對於一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間
(2).對於順序結構,需要依次執行一系列語句所用的時間可採用大O下"求和法則"
求和法則:是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))
特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))
(3).對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間
(4).對於循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"
乘法法則: 是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))
(5).對於復雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法法則技術整個演算法的時間復雜度
另外還有以下2個運演算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數
（5）下面分別對幾個常見的時間復雜度進行示例說明：
(1)、O(1)
Temp=i; i=j; j=temp;
以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。
(2)、O(n2)
2.1. 交換i和j的內容
sum=0； （一次）
for(i=1;i<=n;i++) （n+1次）
for(j=1;j<=n;j++) （n2次）
sum++； （n2次）
解：因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以T(n)= =O(n2)；
2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 語句1的頻度是n-1
語句2的頻度是(n-1)*(2n+1)=2n2-n-1
f(n)=2n2-n-1+(n-1)=2n2-2；
又Θ(2n2-2)=n2
該程序的時間復雜度T(n)=O(n2).
一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分，當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。
(3)、O(n)
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解： 語句1的頻度：2,
語句2的頻度： n,
語句3的頻度： n-1,
語句4的頻度：n-1,
語句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
(4)、O(log2n)
i=1; ①
while (i<=n)
i=i*2; ②
解： 語句1的頻度是1,
設語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=log2n,
T(n)=O(log2n )
(5)、O(n3)
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：當i=m, j=k的時候,內層循環的次數為k當i=m時, j 可以取 0,1,...,m-1 , 所以這里最內循環共進行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環共進行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時間復雜度為O(n3).
（5）常用的演算法的時間復雜度和空間復雜度
一個經驗規則：其中c是一個常量，如果一個演算法的復雜度為c 、 log2n 、n 、 n*log2n ,那麼這個演算法時間效率比較高 ，如果是2n ,3n ,n!，那麼稍微大一些的n就會令這個演算法不能動了，居於中間的幾個則差強人意。
演算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善於從數學層面上探尋其本質，才能准確理解其內涵。
2、演算法的空間復雜度
類似於時間復雜度的討論，一個演算法的空間復雜度(Space Complexity)S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。
空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。演算法的輸入輸出數據所佔用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。存儲演算法本身所佔用的存儲空間與演算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的演算法。演算法在運行過程中臨時佔用的存儲空間隨演算法的不同而異，有的演算法只需要佔用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種演算法是「就地\"進行的，是節省存儲的演算法，如這一節介紹過的幾個演算法都是如此；有的演算法需要佔用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將佔用較多的存儲單元，例如將在第九章介紹的快速排序和歸並排序演算法就屬於這種情況。
如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為0(10g2n)；當一個演算法的空I司復雜度與n成線性比例關系時，可表示為0(n).若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變數的地址，
⑷ C語言平面連桿機構計算機輔助設計
得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。
演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。
二、演算法設計的方法
1.遞推法
遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造演算法的問題有重要的遞推性質，即當得到問題規模為i-1的解後，由問題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為I的解。這樣，程序可從i=0或i=1出發，重復地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。
階乘計算
問題描述：編寫程序，對給定的n（n≤100），計算並輸出k的階乘k！（k=1，2，…，n）的全部有效數字。
由於要求的整數可能大大超出一般整數的位數，程序用一維數組存儲長整數，存儲長整數數組的每個元素只存儲長整數的一位數字。如有m位成整數N用數組a[ ]存儲：
N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
並用a[0]存儲長整數N的位數m，即a[0]=m。按上述約定，數組的每個元素存儲k的階乘k！的一位數字，並從低位到高位依次存於數組的第二個元素、第三個元素……。例如，5！=120，在數組中的存儲形式為：
3 0 2 1 ……
首元素3表示長整數是一個3位數，接著是低位到高位依次是0、2、1，表示成整數120。
計算階乘k！可採用對已求得的階乘(k-1)！連續累加k-1次後求得。例如，已知4！=24，計算5！，可對原來的24累加4次24後得到120。細節見以下程序。
# include <stdio.h>
# include <malloc.h>
......
2.遞歸
遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。
能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。
編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （當n>1時）。
寫成遞歸函數有：
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。
組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為： （1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函數的演算法。設函數為void comb(int m,int k)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[ ]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。
# include <stdio.h>
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(「%4d」,a[j]);
printf(「\n」);
}
}
}
void main()
{ a[0]=3;
comb(5,3);
}
3.回溯法
回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。
組合問題
問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。
採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
（1） a[i+1]>a，後一個數字比前一個大；
（2） a-i<=n-r+1。
按回溯法的思想，找解過程可以敘述如下：
首先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一過程，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。重復上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程序如下：
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a=1;
do {
if (a-i<=m-r+1
{ if (i==r-1)
{ for (j=0;j<r;j++)
printf(「%4d」,a[j]);
printf(「\n」);
}
a++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}
main()
{ comb(5,3);
}
4.貪婪法
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪演算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。
裝箱問題
問題描述：裝箱問題可簡述如下：設有編號為0、1、…、n-1的n種物品，體積分別為v0、v1、…、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V，即對於0≤i＜n，有0＜vi≤V。不同的裝箱方案所需要的箱子數目可能不同。裝箱問題要求使裝盡這n種物品的箱子數要少。
若考察將n種物品的集合分劃成n個或小於n個物品的所有子集，最優解就可以找到。但所有可能劃分的總數太大。對適當大的n，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝箱問題採用非常簡單的近似演算法，即貪婪法。該演算法依次將物品放到它第一個能放進去的箱子中，該演算法雖不能保證找到最優解，但還是能找到非常好的解。不失一般性，設n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然後按排序結果對物品重新編號即可。裝箱演算法簡單描述如下：
{ 輸入箱子的容積；
輸入物品種數n；
按體積從大到小順序，輸入各物品的體積；
預置已用箱子鏈為空；
預置已用箱子計數器box_count為0；
for (i=0;i<n;i++)
{ 從已用的第一隻箱子開始順序尋找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一個箱子，並將物品i放入該箱子；
box_count++；
}
else
將物品i放入箱子j；
}
}
上述演算法能求出需要的箱子數box_count，並能求出各箱子所裝物品。下面的例子說明該演算法不一定能找到最優解，設有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。按上述演算法計算，需三隻箱子，各箱子所裝物品分別為：第一隻箱子裝物品1、3；第二隻箱子裝物品2、4、5；第三隻箱子裝物品6。而最優解為兩只箱子，分別裝物品1、4、5和2、3、6。
若每隻箱子所裝物品用鏈表來表示，鏈表首結點指針存於一個結構中，結構記錄尚剩餘的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上演算法編寫的程序。
}
5.分治法
任何一個可以用計算機求解的問題所需的計算時間都與其規模N有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。
分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
如果原問題可分割成k個子問題（1<k≤n），且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。
分治法所能解決的問題一般具有以下幾個特徵：
（1）該問題的規模縮小到一定的程度就可以容易地解決；
（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
（3）利用該問題分解出的子問題的解可以合並為該問題的解；
（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特徵是應用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。
分治法在每一層遞歸上都有三個步驟：
（1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
（2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
（3）合並：將各個子問題的解合並為原問題的解。
6.動態規劃法
經常會遇到復雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地採用把大問題分解成子問題，並綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。
為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法。以下先用實例說明動態規劃方法的使用。
求兩字元序列的最長公共字元子序列
問題描述：字元序列的子序列是指從給定字元序列中隨意地（不一定連續）去掉若干個字元（可能一個也不去掉）後所形成的字元序列。令給定的字元序列X=「x0，x1，…，xm-1」，序列Y=「y0，y1，…，yk-1」是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。
考慮最長公共子序列問題如何分解成子問題，設A=「a0，a1，…，am-1」，B=「b0，b1，…，bm-1」，並Z=「z0，z1，…，zk-1」為它們的最長公共子序列。不難證明有以下性質：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且「z0，z1，…，zk-2」是「a0，a1，…，am-2」和「b0，b1，…，bn-2」的一個最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列。
這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找「a0，a1，…，am-2」和「b0，b1，…，bm-2」的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列和找出「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
代碼如下：
# include <stdio.h>
# include <string.h>
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[0]=0;
for (i=0;i<=n;i++) c[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];
else
c[j]=c[j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=』』;
while (k>0)
if (c[j]==c[i-1][j]) i--;
else if (c[j]==c[j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (「Enter two string（<%d）!\n」,N);
scanf(「%s%s」,a,b);
printf(「LCS=%s\n」,build_lcs(str,a,b));
}
7.迭代法
迭代法是用於求方程或方程組近似根的一種常用的演算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x)，然後按以下步驟執行：
（1） 選一個方程的近似根，賦給變數x0；
（2） 將x0的值保存於變數x1，然後計算g(x1)，並將結果存於變數x0；
（3） 當x0與x1的差的絕對值還小於指定的精度要求時，重復步驟（2）的計算。
若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述演算法用C程序的形式表示為：
程序如下：
迭代法求方程組的根
{ for (i=0;i<n;i++)
x=初始近似根;
do {
for (i=0;i<n;i++)
y = x;
for (i=0;i<n;i++)
x = gi(X);
for (delta=0.0,i=0;i<n;i++)
if (fabs(y-x)>delta) delta=fabs(y-x)； } while (delta>Epsilon)；
for (i=0;i<n;i++)
printf(「變數x[%d]的近似根是 %f」，I，x)；
printf(「\n」)；
} 具體使用迭代法求根時應注意以下兩種可能發生的情況：
（1）如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；
（2）方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。
8.窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。
將A、B、C、D、E、F這六個變數排成如圖所示的三角形，這六個變數分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變數之和相等的全部解。如圖就是一個解。
程序引入變數a、b、c、d、e、f，並讓它們分別順序取1至6的整數，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變數之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變數取盡所有的組合後，程序就可得到全部可能的解。程序如下：
按窮舉法編寫的程序通常不能適應變化的情況。如問題改成有9個變數排成三角形，每條邊有4個變數的情況，程序的循環重數就要相應改變。
⑸ 演算法的時間復雜度如何計算
求解演算法的時間復雜度的具體步驟是：
⑴ 找出演算法中的基本語句；
演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。
⑵ 計算基本語句的執行次數的數量級；
只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。
⑶ 用大Ο記號表示演算法的時間性能。
將基本語句執行次數的數量級放入大Ο記號中。
如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。
常見的演算法時間復雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效演算法，把這類問題稱為P類問題，而把後者稱為NP問題。
這只能基本的計算時間復雜度，具體的運行還會與硬體有關。
參考博客地址：http://blog.csdn.net/xingqisan/article/details/3206303
⑹ 數據結構，分析時間復雜度，關鍵是告訴我怎麼算
1. 一般情況下,演算法的基本操作重復執行的次數是模塊n的某一個函數f(n),因此,演算法的時間復雜度記做:T(n)=O(f(n)) 分析:隨著模塊n的增大,演算法執行的時間的增長率和f(n)的增長率成正比,所以f(n)越小,演算法的時間復雜...
⑺ 數據結構中演算法的時間復雜度計算，求高手幫忙
0. N^2
1.N^3
2.根號N
3.log(N)