數(shù)據(jù)結(jié)構(gòu)與算法之美 - 學(xué)習(xí)筆記
時(shí)間復(fù)雜度
算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度，記為 T(n)。算法的時(shí)間復(fù)雜度也就是算法的時(shí)間度量，記作 T(n) = O(f(n))。表示隨問題規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長率和 f(n)的增長率相同
大 O 時(shí)間復(fù)雜度表示法
算法的執(zhí)行效率，粗略的講就是算法代碼的執(zhí)行時(shí)間
舉例
假設(shè)每行代碼的執(zhí)行時(shí)間都為 unit_time，估算以下代碼執(zhí)行時(shí)間
int cal(int n) {
int sum = 0; // 1 unit_time
int i = 1; // 1 unit_time
for (; i <= n; ++i) { // n unit_time
sum = sum + i; // n unit_time
}
return sum;
}
總執(zhí)行時(shí)間為 T(n) = (2n+2)*unit_time
int cal(int n) {
int sum = 0; // 1 unit_time
int i = 1; // 1 unit_time
int j = 1; // 1 unit_time
for (; i <= n; ++i) { // n unit_time
j = 1; // n unit_time
for (; j <= n; ++j) { // 循環(huán)嵌套 n^2 unit_time
sum = sum + i * j; // n^2 unit_time
}
}
}
總執(zhí)行時(shí)間為 T(n) = (3+2n+2n^2)*unit_time
推導(dǎo)大 O
T(n) = O(f(n))
T(n)表示代碼的執(zhí)行時(shí)間；n 表示數(shù)據(jù)規(guī)模的大小；f(n)表示每行代碼執(zhí)行的次數(shù)總和，因?yàn)檫@是一個(gè)公式，所以用 f(n)來表示。公式中的 O，表示代碼的執(zhí)行時(shí)間 T(n)與 f(n)表達(dá)式成正比
大 O 時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫做漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度
當(dāng) n 很大時(shí)。公式中的低階、常量、系數(shù)不左右增長趨勢可忽略。只需記錄一個(gè)最大量級即可
拿第二段代碼舉例: 第二段代碼中 T(n) = O(2n^2+2n+3). 在此公式中, 低階是 2n , 常量是 3 , 系數(shù)是 2. 這三部分都不會左右增長趨勢,所以可以忽略，就可記為 T(n)=O(n^2)
時(shí)間復(fù)雜度分析（實(shí)用方法）
1. 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
大 O 這種復(fù)雜度表示方法只是表示一種變化趨勢，忽略公式中常量、低階、系數(shù)，只記錄一個(gè)最大階的量級即可
2. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
如果 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)))
量級最大也就是項(xiàng)的次數(shù)最高
3. 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
如果 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)).
幾種常見時(shí)間復(fù)雜度實(shí)例分析
復(fù)雜度量級（按數(shù)量級遞增）
[圖片上傳失敗...(image-57f5d4-1626169860582)]
NP 問題：時(shí)間復(fù)雜度為非多項(xiàng)式量級的算法問題
當(dāng)數(shù)據(jù)規(guī)模 n 越來越大時(shí)，非多項(xiàng)式量級算法的執(zhí)行時(shí)間會急劇增加，求解問題的執(zhí)行時(shí)間會無限增長。所以，非多項(xiàng)式時(shí)間復(fù)雜度的算法其實(shí)是非常低效的算法（O(2^n)和 O(n!)）
1. 常數(shù)階 O(1) :表示該算法的執(zhí)行時(shí)間總是為一個(gè)常量
// 不論輸入的數(shù)據(jù)集是大是小，只要沒有循環(huán)等復(fù)雜結(jié)構(gòu)，這個(gè)代碼的時(shí)間復(fù)雜度就是常數(shù)階
val i = 1;
var j = 2;
var k = i + j;
2. 線性階 O(n) :表示一個(gè)算法的性能會隨著輸入數(shù)據(jù)的大小變化而線性變化
// 循環(huán)執(zhí)行次數(shù)隨輸入n變化
for (var i = 0; i < n; i++) {
console.log(i);
}
3. 平方階 O(n^2) ：表示一個(gè)算法的性能會隨著輸入數(shù)據(jù)的增長而呈現(xiàn)二次增長，常見為對輸入數(shù)據(jù)進(jìn)行嵌套循環(huán)
// 若不斷嵌套，算法性能將會變?yōu)镺(n^k)
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
console.log(j);
}
}
4. 指數(shù)階 O(2^n) :算法性能隨輸入數(shù)據(jù)每次增加而增大兩倍(斐波那契數(shù)列)
5. 對數(shù)階 O(logn)
// 在while循環(huán)里面，每次都將 i 乘以 2，直到i不小于n退出
// 假設(shè)循環(huán)次數(shù)為x，也就是說 2 的 x 次方等于 n
// 則由2^x=n得出x=log?n。因此這個(gè)代碼的時(shí)間復(fù)雜度為$O(logn)$
var i = 1;
while (i < n) {
i = i * 2;
}
6. 線性對數(shù)階 O(nlogn) :將時(shí)間復(fù)雜度為對數(shù)階 O(logn)的代碼循環(huán) n 遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logN)，也就是了 O(nlogn)
常見算法時(shí)間復(fù)雜度由小到大
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)<O(nn)
[圖片上傳失敗...(image-9277f1-1626169860582)]
Ο(1)表示基本語句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來說，只要算法中不存在循環(huán)語句，其時(shí)間復(fù)雜度就是 Ο(1)。
Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n ^ 2)和 Ο(n ^ 3)稱為多項(xiàng)式時(shí)間，而 Ο(2n)和 Ο(n!)稱為指數(shù)時(shí)間。前者是有效算法，把這類問題稱為 P 類問題，而把后者稱為 NP 問題
空間復(fù)雜度分析
空間復(fù)雜度全稱為漸進(jìn)空間復(fù)雜度，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系
時(shí)間復(fù)雜度還分為：最好/壞情況時(shí)間復(fù)雜度、平均情況時(shí)間復(fù)雜度、均攤時(shí)間復(fù)雜度。根據(jù)具體情況分析
