https://www.cnblogs.com/Allen-win/articles/6816376.html
-寶寶為啥聽不懂他們在討論的時間復雜度 0.0
-我怎么知道這個算法運行得比那個算法快 0.0
-我究竟會不會超時0.0
-我為什么還會超時0.0
-時間復雜度怎么算0.0
在別人還不會求時間復雜度的時候而你會了是不是很酷
在別人都會求時間復雜度的時候而你不會是不是很尷尬
千里之行始于足下
希望這篇文章能祝你一臂之力=w=
此篇詳解，希望能幫助各位稍微解決一下不解=w=
好的算法應該具備時間效率高和存儲量低的特點，這里只介紹前者
一、定義（理解不了沒關系，理解得了還寫什么博客）
?????一般情況下，算法中 基本操作重復執(zhí)行的次數是問題規(guī)模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等 于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度(O是數量級的符號 )，簡稱時間復雜度。
1、咱們來搞懂定義=w=
（1）時間頻度?
一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道算法花費的時間多少（魔鏡魔鏡告訴我，那個算法是跑得快的算法0.0）
????一個算法花費的時間與算法中語句的執(zhí)行次數成正比例，哪個算法中語句執(zhí)行次數多，它花費時間就多。
????一個算法中的語句執(zhí)行次數稱為語句頻度或時間頻度。記為T(n)。
（2）時間復雜度?
?????n稱為問題的規(guī)模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規(guī)律。為此，我們引入時間復雜度概念。?
?????一般情況下，算法中基本操作重復執(zhí)行的次數是問題規(guī)模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n))
????稱Ｏ(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。
注意，時間頻度與時間復雜度是不同的，時間頻度不同但時間復雜度可能相同。
如：T(n)=n^2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n^2)。
常見的時間復雜度有：
常數階O(1)<對數階O(log2n)<線性階O(n),<線性對數階O(nlog2n)
<平方階O(n^2)<方階O(n3)
<指數階O(2^n)
?
?
?
?（3）最壞時間復雜度和平均 時間復雜度 最壞情況下的時間復雜度稱最壞時間復雜度。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。 這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。
?????在最壞情況下的時間復雜度為T(n)=0(n)，它表示對于任何輸入實例,該算法的運行時間不可能大于0(n)。 平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下，算法的期望運行時間。
指數階0(2n)，顯然，時間復雜度為指數階0(2n)的算法效率極低，當n值稍大時就無法應用。
2、最壞時間復雜度和平均時間復雜度
對于時間復雜度的分析，一般是這兩種方法：
（1）最壞時間復雜度
????最壞情況運行時間(運行時間將不會再壞了=A=)。
通常，除非特別指定，我們提到的運行時間都是最壞情況的運行時間
對于追問為什么是最壞時間復雜度的好奇寶寶：
1、如果最差情況下的復雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。（完美=w=）
2、也許你覺得平均情況下的復雜度更吸引你（見下），但是：第一，難計算第二，有很多算法的平均情況和最差情況的復雜度是一樣的. 第三，而且輸入數據的分布函數很可能是你沒法知道。
?
(2)平均時間復雜度
平均時間復雜度也是從概率的角度看，更能反映大多數情況下算法的表現。當然，實際中不可能將所有可能的輸入都運行一遍，因此平均情況通常指的是一種數學期望值，而計算數學期望值則需要對輸入的分布情況進行假設。平均運行時間很難通過分析得到，一般都是通過運行一定數量的實驗數據后估算出來的。
3、閑聊
???到此，基本介紹已經完成了=w=，下一部分就是怎么去計算了，
當你看到這里的時候，
你就能明白那些大犇所說的時間復雜度是個什么鬼，
知道哪個算法跑得快也就是擇優(yōu)的標準（雖然你還不會求=。=），
于是你也能知道在數據范圍下，大概會選用哪種時間復雜度的方法以及你會不會TLE（雖然你還不會求=。=）
舉個栗子（就不給你吃），比如 我要求你在字典里查同一個字，告訴我這個字在字典的那一頁。如果一頁一頁的翻，你需要多少時間呢？最優(yōu)的情況就是這個字在第一頁，最壞的情況就是這個字是 整本字典的最后一個字。所以即使我故意為難你，你也不會花費比找整本字典最后一個字還長的時間。
當然，此時聰明的你就會想用部首、筆畫等去查，才不要傻乎乎的一頁一頁翻，此時的你就會擇優(yōu)選擇，因為此時你最壞得情況就是我給你部首筆畫最多、除部首外筆畫最多的一個超級復雜的一個字，但顯然比翻整本字典快得多。
誒呀，一不小心已經不僅會選擇而且還會優(yōu)化了呢=w=
二、求時間復雜度
1、根據定義，可以歸納出基本的計算步驟
（1.）計算出基本操作的執(zhí)行次數T(n)
基本操作即算法中的每條語句的執(zhí)行次數一般默認為考慮最壞的情況。
（2）計算出T(n)的數量級
求T(n)的數量級，只要將T(n)進行如下一些操作：
?忽略常量、低次冪和最高次冪的系數
令f(n)=T(n)的數量級。
（3）用大O來表示時間復雜度
例:
??for（i=1;i<=n;++i）
??{
?????for(j=1;j<=n;++j)
?????{
?????????c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數：n^2
??????????for(k=1;k<=n;++k)
???????????????c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數：n^3
?????}
??}
??則有 T（n）= n^2+n^3，根據上面括號里的同數量級，我們可以確定 n^3為T（n）的同數量級
??則有f（n）= n^3，然后根據T（n）/f（n）求極限可得到常數c
??則該算法的 時間復雜度：T（n）=O（n^3)
2、于是我們發(fā)現根本沒必要都算，所以我們有了精簡后的步驟：
1.找到執(zhí)行次數最多的語句
2. 計算語句執(zhí)行次數的數量級
3. 用大O來表示結果?
eg:
(1) ??for(i=1;i<=n;i++) ????//循環(huán)了n*n次，當然是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無關
（7）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)是常數0。
綜上：
1、取決于執(zhí)行次數最多的語句，如當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數最多的循環(huán)語句中最內層語句的頻度f(n)決定的。
2、如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數。此類算法的時間復雜度是O(1)
3、算法的時間復雜度不僅僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關。
?
3、閑聊
好了，到此為止，你已經會了求時間復雜的基本方法，可以找出你手中的代碼去求一下就當練習了
讀到這里，考試時或平時應用時便能判斷出你所采用的算法會不會TLE，不再是感覺一定正確的算法結果TLE的一臉震驚和大寫的生無可戀而是一臉胸有成竹的自信和“我就知道是這樣”的淡定。
這個時候我再讓你去那個字在哪頁的時候你就會選擇一種簡約時尚有內涵的方法，并且對你需要做多少步、翻多少頁能做到心中有數，而不是累死累活的一頁一頁翻一邊翻還一邊畫個圈圈詛咒我=。=（怪我嘍）
?——by Eirlys
轉自：http://blog.csdn.net/eirlys_north/article/details/52959540
