一、算法效率的度量方法
1.事后統(tǒng)計方法
這種方法主要是通過設(shè)計好的測試程序和數(shù)據(jù)胆萧，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。
2.事前分析估算方法
在計算機程序編寫前运吓，依據(jù)統(tǒng)計方法對算法進行估算。
經(jīng)過總結(jié)疯趟，我們發(fā)現(xiàn)一個高級語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素：
算法采用的策略拘哨，方案
編譯產(chǎn)生的代碼質(zhì)量
問題的輸入規(guī)模
機器執(zhí)行指令的速度
由此可見，拋開這些與計算機硬件信峻、軟件有關(guān)的因素倦青，一個程序的運行時間依賴于算法的好壞和問題的輸入規(guī)模。（所謂的問題輸入規(guī)模是指輸入量的多少）
實現(xiàn)：1+2+…+99+100
第一種算法：
int i, sum = 0, n = 100; // 執(zhí)行1次
for( i=1; i <= n; i++ ) // 執(zhí)行了n+1次
{
sum = sum + i; // 執(zhí)行n次
}
第二種算法：
int sum = 0, n = 100; // 執(zhí)行1次
sum = (1+n)*n/2; // 執(zhí)行1次
第一種算法執(zhí)行了1+(n+1)+n=2n+2次盹舞。
第二種算法产镐，是1+1=2次
如果我們把循環(huán)看做一個整體，忽略頭尾判斷的開銷踢步，那么這兩個算法其實就是n和1的差距癣亚。
分析一個算法的運行時間時，重要的是把基本操作的數(shù)量和輸入模式關(guān)聯(lián)起來获印。
二述雾、函數(shù)的漸近增長
例1：
假設(shè)兩個算法的輸入規(guī)模都是n，
算法A要做2n+3次操作，即：先執(zhí)行n次的循環(huán)玻孟，執(zhí)行完成后再有一個n次的循環(huán)唆缴，最后有3次運算。
算法B要做3n+1次操作取募，理解同上
哪一個更快些琐谤？
當(dāng)n=1時，算法A1效率不如算法B1玩敏，
當(dāng)n=2時斗忌，兩者效率相同；
當(dāng)n>2時旺聚，算法A1就開始優(yōu)于算法B1了织阳，隨著n的繼續(xù)增加，算法A1比算法B1 逐步拉大差距砰粹。所以總體上算法A1比算法B1優(yōu)秀唧躲。
函數(shù)的漸近增長：給定兩個函數(shù)f(n)和g(n)，如果存在一個整數(shù)N碱璃，使得對于所有的n>N弄痹，f(n)總是比g(n)大，那么嵌器，我們說f(n)的增長漸近快于g(n)肛真。
注：隨著n的增大，后面的+3和+1其實是不影響最終的算法變化曲線的爽航。所以蚓让，我們可以忽略這些加法常數(shù)。
例2：算法C是4n+8讥珍，算法D是2n^2+1历极。
去掉與n相乘的常數(shù)，兩者的結(jié)果還是沒有改變衷佃，算法C2的次數(shù)隨著n的增長趟卸，還是遠小于算法D2。也就是說氏义，與最高次項相乘的常數(shù)并不重要衰腌，也可以忽略。
例3：算法E是2n2+3n+1觅赊，算法F是2n3+3n+1
例4：算法G是2n^2，算法H是3n+1琼稻，算法I是 2n^2+3n+1
當(dāng)他們數(shù)據(jù)很小的時候是這樣的：
這組數(shù)據(jù)我們看得很清楚吮螺，當(dāng)n的值變得非常大的時候，3n+1已經(jīng)沒法和2n^2的結(jié)果相比較，最終幾乎可以忽略不計鸠补。而算法G在跟算法I基本已經(jīng)重合了萝风。
于是我們可以得到這樣一個結(jié)論，判斷一個算法的效率時紫岩，函數(shù)中的常數(shù)和其他次要項常彻娑瑁可以忽略，而更應(yīng)該關(guān)注主項（最高項）的階數(shù)泉蝌。
三歇万、算法時間復(fù)雜度
1.算法時間復(fù)雜度的定義：
在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)勋陪，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級贪磺。算法的時間復(fù)雜度，也就是算法的時間量度诅愚，記作：T(n)= O(f(n))寒锚。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同违孝，稱作算法的漸近時間復(fù)雜度刹前，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的某個函數(shù)雌桑。
用大寫O()來體現(xiàn)算法時間復(fù)雜度的記法喇喉，我們稱之為大O記法。
一般情況下筹燕，隨著輸入規(guī)模n的增大轧飞，T(n)增長最慢的算法為最優(yōu)算法。
顯然撒踪，由此算法時間復(fù)雜度的定義可知过咬，我們的三個求和算法的時間復(fù)雜度分別為O(1)，O(n)制妄，O(n^2)掸绞。
2.推導(dǎo)大O階方法
如何分析一個算法的時間復(fù)雜度呢？即如何推導(dǎo)大O階呢耕捞？
- 用常數(shù)1取代運行時間中的所有加法常數(shù)衔掸。
- 在修改后的運行次數(shù)函數(shù)中，只保留最高階項俺抽。
- 如果最高階項存在且不是1敞映，則去除與這個項相乘的常數(shù)。
- 得到的最后結(jié)果就是大O階磷斧。
①常數(shù)階
例：段代碼的大O是多少振愿？
int sum = 0, n = 100;
printf(“I love you.com\n”);
printf(“I love you.com\n”);
printf(“I love you.com\n”);
printf(“I love you.com\n”);
printf(“I love you.com\n”);
printf(“I love you.com\n”);
sum = (1+n)*n/2;
第一條就說明了所有加法常數(shù)給他個O(1)即可
②線性階：一般含有非嵌套循環(huán)涉及線性階捷犹，線性階就是隨著問題規(guī)模n的擴大，對應(yīng)計算次數(shù)呈直線增長冕末。
int i , n = 100, sum = 0;
for( i=0; i < n; i++ )
{
sum = sum + I;
}
上面這段代碼萍歉，它的循環(huán)的時間復(fù)雜度為O(n)，因為循環(huán)體中的代碼需要執(zhí)行n次档桃。
③平方階
int i, j, n = 100;
for( i=0; i < n; i++ )
{
for( j=0; j < n; j++ )
{
printf(“I love FishC.com\n”);
}
}
n等于100枪孩，也就是說外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)就執(zhí)行100次藻肄，那總共程序想要從這兩個循環(huán)出來蔑舞，需要執(zhí)行100*100次，也就是n的平方仅炊。所以這段代碼的時間復(fù)雜度為O(n^2)斗幼。
總結(jié)：如果有三個這樣的嵌套循環(huán)就是n^3。所以總結(jié)得出抚垄，循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運行的次數(shù)蜕窿。
int i, j, n = 100;
for( i=0; i < n; i++ )
{
for( j=i; j < n; j++ )
{
printf(“I love FishC.com\n”);
}
}
由于當(dāng)i=0時，內(nèi)循環(huán)執(zhí)行了n次呆馁，當(dāng)i=1時桐经，內(nèi)循環(huán)則執(zhí)行n-1次……當(dāng)i=n-1時，內(nèi)循環(huán)執(zhí)行1次浙滤，所以總的執(zhí)行次數(shù)應(yīng)該是：
n+(n-1)+(n-2)+…+1 = n(n+1)/2
n(n+1)/2 = n^2/2+n/2
用我們推導(dǎo)大O的攻略阴挣，第一條忽略，因為沒有常數(shù)相加纺腊。第二條只保留最高項畔咧，所以n/2這項去掉。第三條揖膜，去除與最高項相乘的常數(shù)誓沸，最終得O(n^2)。
④對數(shù)階
int i = 1, n = 100;
while( i < n )
{
i = i * 2;
}
由于每次i*2之后壹粟，就距離n更近一步拜隧，假設(shè)有x個2相乘后大于或等于n，則會退出循環(huán)趁仙。
于是由2^x = n得到x = log(2)n洪添，所以這個循環(huán)的時間復(fù)雜度為O(logn)。
四雀费、函數(shù)調(diào)用的時間復(fù)雜度分析
例：
int i, j;
for(i=0; i < n; i++) {
function(i);
}
void function(int count) {
printf(“%d”, count);
}
函數(shù)體是打印這個參數(shù)干奢，這很好理解。function函數(shù)的時間復(fù)雜度是O(1)盏袄，所以整體的時間復(fù)雜度就是循環(huán)的次數(shù)O(n)律胀。
假如function是下面這樣：
void function(int count) {
int j;
for(j=count; j < n; j++) {
printf(“%d”, j);
}
}
事實上宋光，這和之前平方階的時候舉的第二個例子一樣：function內(nèi)部的循環(huán)次數(shù)隨count的增加(接近n)而減少，所以根據(jù)游戲攻略算法的時間復(fù)雜度為O(n^2)炭菌。
例：
n++; //1
function(n); //1
for(i=0; i < n; i++) { //n
function(i);
}
for(i=0; i < n; i++) { //n^2
for(j=i; j < n; j++) {
printf(“%d”, j);
}
}
void function(int count) {
printf(“%d”, count);
}
為：1+1+n+n2，所以最后是O(n2)
對應(yīng)的線性圖：
常用的時間復(fù)雜度所耗費的時間從小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
五逛漫、最壞情況與平均情況
我們查找一個有n個隨機數(shù)字數(shù)組中的某個數(shù)字黑低，最好的情況是第一個數(shù)字就是，那么算法的時間復(fù)雜度為O(1)酌毡，但也有可能這個數(shù)字就在最后一個位置克握，那么時間復(fù)雜度為O(n)。
平均運行時間是期望的運行時間枷踏。
最壞運行時間是一種保證菩暗。在應(yīng)用中，這是一種最重要的需求旭蠕，通常除非特別指定停团，我們提到的運行時間都是最壞情況的運行時間。
五掏熬、算法的空間復(fù)雜度
我們在寫代碼時佑稠，完全可以用空間來換去時間。
舉個例子說旗芬，要判斷某年是不是閏年舌胶，你可能會花一點心思來寫一個算法，每給一個年份疮丛，就可以通過這個算法計算得到是否閏年的結(jié)果幔嫂。
另外一種方法是，事先建立一個有2050個元素的數(shù)組誊薄，然后把所有的年份按下標(biāo)的數(shù)字對應(yīng)履恩，如果是閏年，則此數(shù)組元素的值是1暇屋，如果不是元素的值則為0似袁。這樣，所謂的判斷某一年是否為閏年就變成了查找這個數(shù)組某一個元素的值的問題咐刨。
第一種方法相比起第二種來說很明顯非常節(jié)省空間昙衅，但每一次查詢都需要經(jīng)過一系列的計算才能知道是否為閏年。第二種方法雖然需要在內(nèi)存里存儲2050個元素的數(shù)組定鸟，但是每次查詢只需要一次索引判斷即可而涉。
這就是通過一筆空間上的開銷來換取計算時間開銷的小技巧。到底哪一種方法好联予？其實還是要看你用在什么地方啼县。
定義：算法的空間復(fù)雜度通過計算算法所需的存儲空間實現(xiàn)材原，算法的空間復(fù)雜度的計算公式記作：S(n)=O(f(n))，其中季眷，n為問題的規(guī)模余蟹，f(n)為語句關(guān)于n所占存儲空間的函數(shù)。
通常子刮，我們都是用“時間復(fù)雜度”來指運行時間的需求威酒，是用“空間復(fù)雜度”指空間需求。
當(dāng)直接要讓我們求“復(fù)雜度”時挺峡，通常指的是時間復(fù)雜度葵孤。
顯然對時間復(fù)雜度的追求更是屬于算法的潮流！
