1、復(fù)雜度分析
數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題塘娶，即如何讓代碼運行得更快归斤，更省存儲空間。執(zhí)行效率是算法一個非常重要的考量指標(biāo)刁岸。那如何來衡量你編寫的算法代碼的執(zhí)行效率呢脏里？
事后統(tǒng)計法：依賴測試環(huán)境，受數(shù)據(jù)規(guī)模影響大虹曙，標(biāo)準(zhǔn)難把控迫横。
復(fù)雜度分析：不利用測試數(shù)據(jù)，粗略估算代碼的執(zhí)行效率酝碳，指導(dǎo)編碼矾踱。
2.大 O 復(fù)雜度表示法
從 CPU 的角度來看，這段代碼的每一行都執(zhí)行著類似的操作：讀數(shù)據(jù)-運算-寫數(shù)據(jù).
假設(shè)每一次執(zhí)行所花時間都為都unix_time.總共執(zhí)行次數(shù)為f(n),總共執(zhí)行時間為T(n),
示例1:
?int cal(int n) {
?? int sum = 0;
?? int i = 1;
?? for (; i <= n; ++i) {
?? ? sum = sum + i;
?? }
?? return sum;
?}
示例2:
?int cal(int n) {
?? int sum = 0;
?? int i = 1;
?? int j = 1;
?? for (; i <= n; ++i) {
?? ? j = 1;
?? ? for (; j <= n; ++j) {
?? ? ? sum = sum +? i * j;
?? ? }
?? }
?}
所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? T(n) = O(f(n))
大 O 時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行時間疏哗，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢呛讲，所以，也叫作漸進時間復(fù)雜度（asymptotic time complexity），簡稱時間復(fù)雜度贝搁。
3.時間復(fù)雜度分析
? ? 大 O 這種復(fù)雜度表示方法只是表示一種變化趨勢吗氏。我們通常會忽略掉公式中的常量、低階雷逆、系數(shù)弦讽，只需要記錄一個最大階的量級就可以了。
只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼关面。
2. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
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. 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
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;
?}
4.幾種常見時間復(fù)雜度實例分析
? ? ?代碼生涯所能接觸到的幾乎所有復(fù)雜度量級:
常見的復(fù)雜度并不多坦袍，從低階到高階有：O(1)、O(logn)等太、O(n)捂齐、O(nlogn)、O(n2 )缩抡。幾乎所有的數(shù)據(jù)結(jié)構(gòu)和算法的復(fù)雜度都跑不出這幾個奠宜。
1. O(1)
示例：
?int i = 8;
?int j = 6;
?int sum = i + j;
2. O(logn)、O(nlogn)
示例：
?i=1;
?while (i <= n)? {
?? i = i * 2;
?}
歸并排序瞻想、快速排序压真、堆排序的時間復(fù)雜度都是 O(nlogn)。
5.空間復(fù)雜度分析
空間復(fù)雜度全稱就是漸進空間復(fù)雜度（asymptotic space complexity）蘑险，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系滴肿。
void print(int n) {
? int i = 0;
? int[] a = new int[n];
? for (i; i
? ? a[i] = i * i;
? }
? for (i = n-1; i >= 0; --i) {
? ? print out a[i]
? }
}
我們常見的空間復(fù)雜度就是 O(1)、O(n)佃迄、O(n2 )泼差。
6.最好、最壞呵俏、平均時間復(fù)雜度
// n表示數(shù)組array的長度
int find(int[] array, int n, int x) {
? int i = 0;
? int pos = -1;
? for (; i < n; ++i) {
? ? if (array[i] == x) pos = i;
? }
? return pos;
}
優(yōu)化：
// n表示數(shù)組array的長度
int find(int[] array, int n, int x) {
? int i = 0;
? int pos = -1;
? for (; i < n; ++i) {
? ? if (array[i] == x) {
?? ? ? pos = i;
?? ? ? break;
? ? }
? }
? return pos;
}
最好情況時間復(fù)雜度就是堆缘，在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度普碎。
最壞情況時間復(fù)雜度就是吼肥，在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度麻车。
最好情況時間復(fù)雜度和最壞情況時間復(fù)雜度對應(yīng)的都是極端情況下的代碼復(fù)雜度缀皱，發(fā)生的概率其實并不大。為了更好地表示平均情況下的復(fù)雜度动猬，我們需要引入另一個概念：平均時間復(fù)雜度唆鸡。
要查找的變量 x 在數(shù)組中的位置，有 n+1 種情況：在數(shù)組的 0～n-1 位置中和不在數(shù)組中枣察。
我們假設(shè)在數(shù)組中與不在數(shù)組中的概率都為 1/2。另外，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 這 n 個位置的概率也是一樣的序目，為 1/n臂痕。所以，根據(jù)概率乘法法則猿涨，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 中任意位置的概率就是 1/(2n)握童。
這個值就是概率論中的加權(quán)平均值，也叫作期望值叛赚，所以平均時間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度澡绩。
用大 O 表示法來表示，去掉系數(shù)和常量俺附，這段代碼的加權(quán)平均時間復(fù)雜度為O(n)肥卡。
