分析復雜度三個方法：
1.只關注循環(huán)執(zhí)行次數(shù)最多的一段代碼
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
unit_time為一行代碼執(zhí)行時間
T(n) = (2 + 2n) * unit_time
f(n)為每行代碼執(zhí)行的次數(shù)總和
T(n) = O( f(n) ) = O(2 + 2n)
由于公式中的低階椰棘、常量亡嫌、系數(shù)三部分并不左右增長趨勢送滞，所以都可以忽略凳怨。
T(n) = O(n)
2.加法法則：總復雜度等于量級最大的那段代碼的復雜度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
這段代碼分為3部分，分別為求sum_1、sum_2、sum_3，其中sum_1執(zhí)行次數(shù)為100次由于是常量即使是100000次都與n無關刨沦，當n無限大時就可以忽略。第二段和第三段代碼時間復雜度分別為O(n)和O(n2)膘怕。綜合這三部分的時間復雜度想诅，選取最大量級因此這段代碼的時間復雜度為為O(n2)。
總結：總的時間復雜度就等于量級最大的那段代碼的時間復雜度岛心。抽象為公式：
如果 T1(n)=O(f(n))来破，T2(n)=O(g(n)) 那么 T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n), g(n)))
3.乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
類比加法公式可得乘法公式為：
如果 T1(n)=O(f(n))，T2(n)=O(g(n));那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
單獨看cal()忘古，假設f()為普通操作徘禁，那么T1(n)=O(n)。但f()的時間復雜度為T2(n)=O(n),所以整個cal()的時間復雜度為
T(n)=T1(n)T2(n)=O(nn)=O(n2)
常見時間復雜度：
復雜度量級可分為多項式量級和非多項式量級髓堪。上表中僅指數(shù)階和階乘階為非多項量級送朱，隨著n變大，非多項式量級算法執(zhí)行時間會急劇增加干旁，因此非多項式時間復雜度算法是非常低效的算法驶沼。
1. O(1)
只要代碼的執(zhí)行時間不隨n的增大而增大，這樣代碼的時間復雜度都記為O(1)争群。一般情況下回怜，只要算法中不存在循環(huán)語句、遞歸語句换薄，無論有多少代碼時間復雜度都為O(1)
2. O(logn)玉雾、O(nlogn)
int i = 1;
while (i <= n) {
i = i * 2;
}
每一次循環(huán)i的值乘以2翔试，因此i的取值為等比數(shù)列，如下圖：
求得x即為代碼執(zhí)行次數(shù)复旬，求得
,時間復雜度為
另：無論以幾為底,都可以把對數(shù)階的時間復雜度寫為記為垦缅。如
,可得:
由于前者為常量系數(shù)因此在計算時間復雜度時可以忽略。因此在時間復雜度中我們忽略對數(shù)底驹碍，統(tǒng)一表示為失都。利用上文講述的乘法法則，當循環(huán)n次執(zhí)行
的代碼時幸冻，時間復雜度即為
。歸并排序咳焚，快速排序時間復雜度都為
洽损。
3. O(m+n)、O(m*n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
由于我們無語預知m與n革半，因此無法判斷m與n的量級誰更大碑定，不能進行省略，因此上文中的加法原則在此處并不適用又官，上述代碼的時間復雜度為延刘。
在這種情況下，原先加法法則不正確六敬，我們需要修改加法法則為：
乘法法則仍然有效為：
