一醉途、定義
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)殴穴，用T(n)表示货葬，若有某個(gè)輔助函數(shù)f(n)震桶，使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)蹲姐，則稱f(n)是T(n)的同數(shù)量級函數(shù)柴墩。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級的符號 )拐邪，簡稱時(shí)間復(fù)雜度。
1) 時(shí)間頻度
- 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間扎阶，從理論上是不能算出來的，必須上機(jī)運(yùn)行測試才能知道着饥。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試宰掉，只需知道算法花費(fèi)的時(shí)間多少
- 一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多孟害，它花費(fèi)時(shí)間就多挪拟。
- 一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)谎柄。
2) 時(shí)間復(fù)雜度
- n稱為問題的規(guī)模惯雳，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會不斷變化捍歪。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律鸵钝。為此，我們引入時(shí)間復(fù)雜度概念变逃。
- 一般情況下怠堪，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示凰棉，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)陌粹，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)或舞。記作T(n)=Ｏ(f(n))
- 稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度映凳，簡稱時(shí)間復(fù)雜度。
注意仆救，時(shí)間頻度與時(shí)間復(fù)雜度是不同的矫渔，時(shí)間頻度不同但時(shí)間復(fù)雜度可能相同。
如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同范嘱，都為O(n2)丑蛤。
常見的時(shí)間復(fù)雜度有：
常數(shù)階O(1)
<對數(shù)階O(log2n)
<線性階O(n)
<線性對數(shù)階O(nlog2n)
<平方階O(n^2)
<方階O(n3)
<指數(shù)階O(2^n)
3) 最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度
最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度受裹。一般不特別說明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度厦章。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界照藻，這就保證了算法的運(yùn)行時(shí)間不會比任何更長。
在最壞情況下的時(shí)間復(fù)雜度為T(n)=0(n)群发，它表示對于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于0(n)发乔。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下栏尚，算法的期望運(yùn)行時(shí)間。
指數(shù)階0(2n)告材，顯然，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低缰猴，當(dāng)n值稍大時(shí)就無法應(yīng)用疤剑。
-- 最壞時(shí)間復(fù)雜度
通常，除非特別指定疑故，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間
為什么是最壞時(shí)間復(fù)雜度：
- 如果最差情況下的復(fù)雜度符合我們的要求弯菊，我們就可以保證所有的情況下都不會有問題。
- 也許你覺得平均情況下的復(fù)雜度更吸引你（見下）钦铁，但是：第一才漆，難計(jì)算第二醇滥，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的. 第三，輸入數(shù)據(jù)的分布函數(shù)很可能是你沒法知道阅虫。
-- 平均時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度也是從概率的角度看不跟，更能反映大多數(shù)情況下算法的表現(xiàn)。當(dāng)然躲履，實(shí)際中不可能將所有可能的輸入都運(yùn)行一遍聊闯，因此平均情況通常指的是一種數(shù)學(xué)期望值，而計(jì)算數(shù)學(xué)期望值則需要對輸入的分布情況進(jìn)行假設(shè)菱蔬。平均運(yùn)行時(shí)間很難通過分析得到史侣，一般都是通過運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來的惊橱。
最后：
1箭昵、時(shí)間復(fù)雜度取決于執(zhí)行次數(shù)最多的語句家制，如當(dāng)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的
2颤殴、如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句杈绸，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)矮瘟。此類算法的時(shí)間復(fù)雜度是O(1)
3芥永、算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模钝吮，還與輸入實(shí)例的初始狀態(tài)有關(guān)
