復雜度分析的必要性：

當給我們一段代碼時，我們是以什么準則來判斷代碼效率的高低呢？每一段代碼都會消耗一段時間，或占據一段數據空間，那么自然是在實現相同功能的情況下，代碼所耗時間最少，所占據空間最小的代碼效率更優。所以對于所耗時間，我們采用時間復雜度進行分析，對于所占空間，我們采用空間復雜度進行分析。

時間復雜度：

在問題中，我們將題目中數據的頻數成為n。一個算法中的語句執行次數稱為語句頻度或時間頻度，記為T(n)。我們想要知道當n不斷變化時，T（n）的變化規律。若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。

大O符號表示法的引入：

下面我們先來看這一段代碼：

1|for(i=1; i<=n; ++i)
2|{
3|  j = i;
4|  j++;
5|}

假設每行代碼的執行時間都是相同的，假設為1。

則第1行執行時間是1，第3行執行時間為n，第4行執行時間為n。所以有T(n) = (2n + 1)，

有當n趨于無窮大時，+1， 與*2 的意義可以忽略。所以時間復雜度記為O（n）。

常見的時間復雜度量級：

常數階O(1)
對數階O(logN)
線性階O(n)
線性對數階O(nlogN)
平方階O(n2)
立方階O(n3)
K次方階O(nk)
指數階(2n)

復雜度從上到下越來越大，執行效率越來越低下

下面對一些復雜度舉例分析：

1，常數階——無論有多少行，其復雜度不隨n的變化而變化。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

?2，線性階O(n):

如上文舉例所示。

3，對數階O(logN)：

int i = 1;
while(i<n)
{i = i * 2;
}

while循環中，將i * 2，i變化的越來越快，離n也越來越近。假設循環x次后，i就大于2了；所以有

2的x次方等于n，所以x = log2^n,所以代碼的時間復雜度為O(logN)；

4，線性對數階O(NlogN)：

就是將線性階循環N次，便是線性對數階。

for(m=1; m<n; m++)
{i = 1;while(i<n){i = i * 2;}
}

5，k次方階：

就是k層循環嵌套。

經典算法的時間復雜度分析：

一般算法題或筆試題的時間限制為1s，或2s以內；故c++的操作次數一般控制在10^7 ~ 10^8為佳。

log(10^x)≈3*x。

調和級數的時間復雜度為O（logN）；

分母只取質數的調和級數時間復雜度為O（loglogN）；

而在不同數據范圍內，應該選擇怎樣的算法與時間復雜度：

· 當N <= 30, ——指數級別，dfs + 剪枝，狀壓DP；

· 當N <= 100, ——O（N^3） 或O（N^3 logN） floyd算法，或普通dp

· 當N <= 1000.——O(N^2) 或 O(N ^ 2 logN)? dp,? 二分

· 當N <= 10000 —— O(N *?)，塊狀鏈表。

· 當N? <= 10^5——O（N logN），各種排序，線段樹，樹狀數組，set/map，heap，堆優化版Dijkstra，spfa，二分，求半平面交

· 當N <= 10^6 —— O（N）以及常數較小的O（NlogN）hash，單調隊列，雙指針，BFS，并查集，kmp，AC自動機。（常數較小的O（NlogN））sort、樹狀數組、heap、dijkstra、spfa

·當N ≤ 10^7——?O(n)雙指針掃描、kmp、AC自動機、線性篩素數

· 當N <= 10^9——O() 判斷質數，試除法求質數，試除法求所有約數，試除法分解質因數

` 當N <= 10 ^ 18——O（logN）最大公約數，快速冪，數位DP

· 當n≤10^1000——O（logN * loglogN）k表示位數，高精度加減乘除
?