0，時間復雜度是指執(zhí)行算法所需要的計算工作量
1，在計算時間復雜度的時候黄痪，先找出算法的基本操作不从，然后根據(jù)相應的各語句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級（它的同數(shù)量級有以下：1卷中，log2n，n，n log2n 塘秦，n的平方，n的三次方动看，2的n次方尊剔，n!），找出后菱皆，f(n) = 該數(shù)量級须误，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時間復雜度T(n) = O(f(n))
例：算法：
for(i=1;?i<=n;?++i)
{
for(j=1;?j<=n;?++j)
{
c[i][j]?=?0;//該步驟屬于基本操作執(zhí)行次數(shù)：n的平方次
for(k=1;?k<=n;?++k)
c[i][j]?+=?a[i][k]?*?b[k][j];//該步驟屬于基本操作執(zhí)行次數(shù)：n的三次方次
}
}
則有 T(n) = n 的平方+n的三次方仇轻，根據(jù)上面括號里的同數(shù)量級京痢，我們可以確定 n的三次方 為T（n）的同數(shù)量級
則有 f(n) = n的三次方，然后根據(jù) T(n)/f(n) 求極限可得到常數(shù)c
則該算法的時間復雜度：T(n) = O(n^3) 注：n^3即是n的3次方拯田。
2历造，在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環(huán)，只有一重則時間復雜度為O(n)吭产，二重則為O(n^2)侣监，依此類推，如果有二分則為O(logn)臣淤，二分例如快速冪橄霉、二分查找，如果一個for循環(huán)套一個二分邑蒋，那么時間復雜度則為O(nlogn)姓蜂。
3，算法的時間復雜度和空間復雜度合稱為算法的復雜度医吊。
1）.時間復雜度
（1）時間頻度一個算法執(zhí)行所耗費的時間钱慢，從理論上是不能算出來的，必須上機運行測試才能知道卿堂。但我們不可能也沒有必要對每個算法都上機測試束莫，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了草描。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例览绿，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多穗慕。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度饿敲。記為T(n)。
（2）時間復雜度?在剛才提到的時間頻度中逛绵，n稱為問題的規(guī)模怀各，當n不斷變化時，時間頻度T(n)也會不斷變化暑脆。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律渠啤。為此，我們引入時間復雜度概念添吗。 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)份名，用T(n)表示碟联，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)僵腺，則稱f(n)是T(n)的同數(shù)量級函數(shù)鲤孵。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度辰如。
時間頻度不同普监，但時間復雜度可能相同。如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同凯正，但時間復雜度相同桑滩，都為O(n2)。
按數(shù)量級遞增排列胁澳，常見的時間復雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...陆盘， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大酸员，上述時間復雜度不斷增大，算法的執(zhí)行效率越低邀泉。
（3）最壞時間復雜度和平均時間復雜度最壞情況下的時間復雜度稱最壞時間復雜度拔恰。一般不特別說明颜懊，討論的時間復雜度均是最壞情況下的時間復雜度匠璧。 這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界鲁僚，這就保證了算法的運行時間不會比任何更長执虹。
在最壞情況下的時間復雜度為T(n)=0(n)侥啤，它表示對于任何輸入實例,該算法的運行時間不可能大于0(n)。 平均時間復雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下赁炎，算法的期望運行時間放棒。
指數(shù)階0(2n)吴旋，顯然，時間復雜度為指數(shù)階0(2n)的算法效率極低忍啤，當n值稍大時就無法應用鳄梅。
（4）求時間復雜度
【1】如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復雜度是O(1)。
x=91; y=100;
while(y>0) if(x>100) {x=x-10;y--;} else x++;
解答： T(n)=O(1)，
這個程序看起來有點嚇人，總共循環(huán)運行了1100次，但是我們看到n沒有?
沒才菠。這段程序的運行是和n無關的，
就算它再循環(huán)一萬年贡定，我們也不管他赋访，只是一個常數(shù)階的函數(shù)
【2】當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的缓待。
x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
該程序段中頻度最大的語句是(5)蚓耽，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關系，但是卻與外層循環(huán)的變量取值有關旋炒，而最外層循環(huán)的次數(shù)直接與n有關步悠，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：??則該程序段的時間復雜度為T(n)=O(n3/6+低次項)=O(n3)
【3】算法的時間復雜度不僅僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關瘫镇。
在數(shù)值A[0..n-1]中查找給定值K的算法大致如下：
i=n-1;
while(i>=0&&(A[i]!=k))
i--;
return i;
此算法中的語句(3)的頻度不僅與問題規(guī)模n有關鼎兽，還與輸入實例中A的各元素取值及K的取值有關: ①若A中沒有與K相等的元素答姥，則語句(3)的頻度f(n)=n； ②若A的最后一個元素等于K,則語句(3)的頻度f(n)是常數(shù)0谚咬。
（5）時間復雜度評價性能
有兩個算法A1和A2求解同一問題鹦付，時間復雜度分別是T1(n)=100n2，T2(n)=5n3择卦。（1）當輸入量n＜20時敲长，有T1(n)＞T2(n)，后者花費的時間較少秉继。（2）隨著問題規(guī)模n的增大祈噪，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大。即當問題規(guī)模較大時秕噪，算法A1比算法A2要有效地多钳降。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在時間方面的質(zhì)量。在算法分析時腌巾，往往對算法的時間復雜度和漸近時間復雜度不予區(qū)分遂填，而經(jīng)常是將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度，其中的f(n)一般是算法中頻度最大的語句頻度澈蝙。
2）.空間復雜度
一個程序的空間復雜度是指運行完一個程序所需內(nèi)存的大小吓坚。利用程序的空間復雜度，可以對程序的運行所需要的內(nèi)存多少有個預先估計灯荧。一個程序執(zhí)行時除了需要存儲空間和存儲本身所使用的指令礁击、常數(shù)、變量和輸入數(shù)據(jù)外逗载，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間哆窿。程序執(zhí)行時所需存儲空間包括以下兩部分。
（1）固定部分厉斟。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少挚躯、數(shù)值無關。主要包括指令空間（即代碼空間）擦秽、數(shù)據(jù)空間（常量码荔、簡單變量）等所占的空間。這部分屬于靜態(tài)空間感挥。
（2）可變空間缩搅，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等触幼。這部分的空間大小與算法有關硼瓣。
一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))其中n為問題的規(guī)模置谦，S(n)表示空間復雜度巨双。
