https://www.cnblogs.com/Allen-win/articles/6816376.html
-寶寶為啥聽不懂他們在討論的時(shí)間復(fù)雜度 0.0
-我怎么知道這個(gè)算法運(yùn)行得比那個(gè)算法快 0.0
-我究竟會(huì)不會(huì)超時(shí)0.0
-我為什么還會(huì)超時(shí)0.0
-時(shí)間復(fù)雜度怎么算0.0
在別人還不會(huì)求時(shí)間復(fù)雜度的時(shí)候而你會(huì)了是不是很酷
在別人都會(huì)求時(shí)間復(fù)雜度的時(shí)候而你不會(huì)是不是很尷尬
千里之行始于足下
希望這篇文章能祝你一臂之力=w=
此篇詳解，希望能幫助各位稍微解決一下不解=w=
好的算法應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)疏哗，這里只介紹前者
一呛讲、定義（理解不了沒關(guān)系，理解得了還寫什么博客）
?????一般情況下返奉，算法中 基本操作重復(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ù)量級的符號(hào) )，簡稱時(shí)間復(fù)雜度十厢。
1等太、咱們來搞懂定義=w=
（1）時(shí)間頻度?
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的蛮放，必須上機(jī)運(yùn)行測試才能知道缩抡。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試，只需知道算法花費(fèi)的時(shí)間多少（魔鏡魔鏡告訴我包颁，那個(gè)算法是跑得快的算法0.0）
????一個(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)也會(huì)不斷變化泼差。但有時(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)=n^2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同燃逻，都為O(n^2)序目。
常見的時(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í)間不會(huì)比任何更長姆怪。
?????在最壞情況下的時(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)用。
2揪胃、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度
對于時(shí)間復(fù)雜度的分析璃哟，一般是這兩種方法：
（1）最壞時(shí)間復(fù)雜度
????最壞情況運(yùn)行時(shí)間(運(yùn)行時(shí)間將不會(huì)再壞了=A=)氛琢。
通常，除非特別指定随闪，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間
對于追問為什么是最壞時(shí)間復(fù)雜度的好奇寶寶：
1阳似、如果最差情況下的復(fù)雜度符合我們的要求，我們就可以保證所有的情況下都不會(huì)有問題蕴掏。（完美=w=）
2障般、也許你覺得平均情況下的復(fù)雜度更吸引你（見下），但是：第一盛杰，難計(jì)算第二挽荡，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的. 第三，而且輸入數(shù)據(jù)的分布函數(shù)很可能是你沒法知道即供。
?
(2)平均時(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ù)后估算出來的。
3抹锄、閑聊
???到此逆瑞，基本介紹已經(jīng)完成了=w=，下一部分就是怎么去計(jì)算了伙单，
當(dāng)你看到這里的時(shí)候获高，
你就能明白那些大犇所說的時(shí)間復(fù)雜度是個(gè)什么鬼，
知道哪個(gè)算法跑得快也就是擇優(yōu)的標(biāo)準(zhǔn)（雖然你還不會(huì)求=吻育。=）念秧，
于是你也能知道在數(shù)據(jù)范圍下，大概會(huì)選用哪種時(shí)間復(fù)雜度的方法以及你會(huì)不會(huì)TLE（雖然你還不會(huì)求=布疼。=）
舉個(gè)栗子（就不給你吃）摊趾，比如 我要求你在字典里查同一個(gè)字，告訴我這個(gè)字在字典的那一頁游两。如果一頁一頁的翻严就，你需要多少時(shí)間呢？最優(yōu)的情況就是這個(gè)字在第一頁器罐，最壞的情況就是這個(gè)字是 整本字典的最后一個(gè)字梢为。所以即使我故意為難你，你也不會(huì)花費(fèi)比找整本字典最后一個(gè)字還長的時(shí)間。
當(dāng)然铸董，此時(shí)聰明的你就會(huì)想用部首祟印、筆畫等去查，才不要傻乎乎的一頁一頁翻粟害，此時(shí)的你就會(huì)擇優(yōu)選擇蕴忆，因?yàn)榇藭r(shí)你最壞得情況就是我給你部首筆畫最多、除部首外筆畫最多的一個(gè)超級復(fù)雜的一個(gè)字悲幅，但顯然比翻整本字典快得多套鹅。
誒呀，一不小心已經(jīng)不僅會(huì)選擇而且還會(huì)優(yōu)化了呢=w=
二汰具、求時(shí)間復(fù)雜度
1卓鹿、根據(jù)定義，可以歸納出基本的計(jì)算步驟
（1.）計(jì)算出基本操作的執(zhí)行次數(shù)T(n)
基本操作即算法中的每條語句的執(zhí)行次數(shù)一般默認(rèn)為考慮最壞的情況留荔。
（2）計(jì)算出T(n)的數(shù)量級
求T(n)的數(shù)量級吟孙，只要將T(n)進(jìn)行如下一些操作：
?忽略常量、低次冪和最高次冪的系數(shù)
令f(n)=T(n)的數(shù)量級聚蝶。
（3）用大O來表示時(shí)間復(fù)雜度
例:
??for（i=1;i<=n;++i）
??{
?????for(j=1;j<=n;++j)
?????{
?????????c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^2
??????????for(k=1;k<=n;++k)
???????????????c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^3
?????}
??}
??則有 T（n）= n^2+n^3杰妓，根據(jù)上面括號(hào)里的同數(shù)量級，我們可以確定 n^3為T（n）的同數(shù)量級
??則有f（n）= n^3碘勉，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c
??則該算法的 時(shí)間復(fù)雜度：T（n）=O（n^3)
2巷挥、于是我們發(fā)現(xiàn)根本沒必要都算，所以我們有了精簡后的步驟：
1.找到執(zhí)行次數(shù)最多的語句
2. 計(jì)算語句執(zhí)行次數(shù)的數(shù)量級
3. 用大O來表示結(jié)果?
eg:
(1) ??for(i=1;i<=n;i++) ????//循環(huán)了n*n次验靡，當(dāng)然是O(n^2)
????????????for(j=1;j<=n;j++)
?????????????????s++;
（2）for(i=1;i<=n;i++) ??//循環(huán)了(n+n-1+...+1)≈(n^2)/2 ,同上 ?????????????????????????????????????????????
???????????for(j=i;j<=n;j++)
?????????????????s++;
(4) ??i=1;k=0;
??????while(i<=n-1){
???????????k+=10*i;
??????i++; ?????}
//循環(huán)了
//n-1≈n次倍宾，所以是O(n)
(5) ??for(i=1;i<=n;i++)
?????????????for(j=1;j<=i;j++)
?????????????????for(k=1;k<=j;k++)
???????????????????????x=x+1;
//循環(huán)了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3，
//即O（n^3)
（6)
x=91; y=100;
while(y>0) if(x>100) {x=x-10;y--;} else x++;
?//T(n)=O(1)晴叨，與n無關(guān)
（7）i=n-1; ???????????
while(i>=0&&(A[i]!=k)) ??????
??????i--; ???????
return i; ??
//此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān): ①若A中沒有與K相等的元素矾屯，則語句(3)的頻度f(n)=n兼蕊； ②若A的最后一個(gè)元素等于K,則語句(3)的頻度f(n)是常數(shù)0。
綜上：
1件蚕、取決于執(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)裳瘪。
?
3土浸、閑聊
好了，到此為止彭羹，你已經(jīng)會(huì)了求時(shí)間復(fù)雜的基本方法黄伊，可以找出你手中的代碼去求一下就當(dāng)練習(xí)了
讀到這里，考試時(shí)或平時(shí)應(yīng)用時(shí)便能判斷出你所采用的算法會(huì)不會(huì)TLE派殷，不再是感覺一定正確的算法結(jié)果TLE的一臉震驚和大寫的生無可戀而是一臉胸有成竹的自信和“我就知道是這樣”的淡定还最。
這個(gè)時(shí)候我再讓你去那個(gè)字在哪頁的時(shí)候你就會(huì)選擇一種簡約時(shí)尚有內(nèi)涵的方法，并且對你需要做多少步毡惜、翻多少頁能做到心中有數(shù)拓轻，而不是累死累活的一頁一頁翻一邊翻還一邊畫個(gè)圈圈詛咒我=。=（怪我嘍）
?——by Eirlys
轉(zhuǎn)自：http://blog.csdn.net/eirlys_north/article/details/52959540
