作為一個(gè)文科生轉(zhuǎn)行過來(lái)的程序媛，數(shù)據(jù)結(jié)構(gòu)和算法的概念對(duì)我來(lái)說(shuō)都是很難。雖然平時(shí)工作幾乎很少用到算法，但是我總覺得如果不懂?dāng)?shù)據(jù)結(jié)構(gòu)，在工作里面，我?guī)缀醪粫?huì)去考慮業(yè)務(wù)之外的東西，比如性能，比如操作數(shù)組的時(shí)候，什么方法是最優(yōu)的，這些都是隱藏需求。是我需要去突破的地方。
所以我決定硬著頭皮啃一下試試。（主要還是跟著老師學(xué)，能不能學(xué)懂我沒有太多信心，但是我希望我可以）
那從今天就進(jìn)入數(shù)據(jù)結(jié)構(gòu)和算法的美妙世界吧！
目的
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法本身需要解決什么問題？
“快” 和“省”! 讓代碼運(yùn)行更快，讓我的代碼更優(yōu)雅，更節(jié)省存儲(chǔ)空間。
雞血??
我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，并不是為了死記硬背幾個(gè)知識(shí)點(diǎn)。我們的目的是建立時(shí)間復(fù)雜度、空間復(fù)雜度意識(shí)，寫出高質(zhì)量的代碼，能夠設(shè)計(jì)基礎(chǔ)架構(gòu)，提升編程技能，訓(xùn)練邏輯思維，積攢人生經(jīng)驗(yàn)，以此獲得工作回報(bào)，實(shí)現(xiàn)你的價(jià)值，完善你的人生。
我被開篇的雞血給打醒了， 哈哈哈哈
第一課，我學(xué)到的知識(shí)
- 學(xué)習(xí)復(fù)雜度分析的好處
老師講了很多關(guān)于復(fù)雜度分析的好處，和事后統(tǒng)計(jì)法的區(qū)別。但是我個(gè)人粗淺的理解是：不用事后統(tǒng)計(jì)，在寫代碼的時(shí)候就考慮自己寫的代碼的時(shí)間,空間復(fù)雜度，就能有效粗略估計(jì)算法的執(zhí)行效率，事先的預(yù)防成本肯定是低于代碼寫好以后再來(lái)優(yōu)化的成本的。
- 大O 復(fù)雜度表示法
從CPU 的角度來(lái)看，代碼的執(zhí)行都是重復(fù)著：讀數(shù)據(jù)-運(yùn)算-寫數(shù)據(jù) 的步驟。當(dāng)我們寫出來(lái)的每一段代碼，如何“肉眼”估算他的計(jì)算時(shí)間呢？
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
上面這個(gè)例子。for 循環(huán)之外的代碼都是運(yùn)行一次，for 循環(huán)里面的代碼運(yùn)行n 次。所以復(fù)雜度就是T(n)
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;
}
}
}
這次的代碼里面有兩個(gè)for 循環(huán)，還是嵌套的for 循環(huán)，那么第一個(gè)for 循環(huán)的運(yùn)行次數(shù)是n ，第二個(gè)是n2
重要點(diǎn)：
所有的代碼執(zhí)行時(shí)間T(n） 和每行代碼的執(zhí)行次數(shù)n 成正比 總結(jié)成公式就是
T(n) = o(f(n))
這就是大 O 時(shí)間復(fù)雜度表示法。大 O 時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以，也叫作漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），簡(jiǎn)稱時(shí)間復(fù)雜度。
時(shí)間復(fù)雜度分析
- 只關(guān)注代碼里面循環(huán)次數(shù)最多的一段代碼，并且排除掉常量，低階, 系數(shù)。
這個(gè)道理還是很好理解的吧，因?yàn)橛绊懘a運(yùn)行的最長(zhǎng)時(shí)間，就是最復(fù)雜的那個(gè)。那些常量不管是多大，他都只會(huì)執(zhí)行一次而已，無(wú)法對(duì)漸進(jìn)時(shí)間復(fù)雜度產(chǎn)生影響， - 加法法則
- 乘法法則： 嵌套代碼的復(fù)雜度等于嵌套內(nèi)外復(fù)雜度的成績(jī)
這個(gè)需要說(shuō)明一下
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;
}
這樣的嵌套循環(huán)里，整個(gè) cal() 函數(shù)的時(shí)間復(fù)雜度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。
貼一個(gè)老師總結(jié)的復(fù)雜度量級(jí)
對(duì)于以上的幾種復(fù)雜度，我來(lái)談一下我自己的理解
O(1)
代碼只會(huì)執(zhí)行一次，是復(fù)雜度最低的，一般來(lái)說(shuō)，只要代碼里不存在循環(huán)語(yǔ)句，遞歸語(yǔ)句，正常的代碼執(zhí)行，不管多少行，他的復(fù)雜度都是O(1)O(logn)、O(nlogn)
一般的循環(huán)，都可以歸為這種的復(fù)雜度里面, 這里再次套用一下老師的一個(gè)例子
i=1;
while (i <= n) {
i = i * 2;
}
這個(gè)例子里面，變量i 從1開始，每循環(huán)一次就乘以2，大于n 的時(shí)候才結(jié)束。
老師說(shuō)這里是高中數(shù)學(xué)里面的等比數(shù)列。我就恍然大悟，然后再去復(fù)習(xí)了一下等比數(shù)列和對(duì)數(shù)。
這里代碼的復(fù)雜度是 x=log2n 實(shí)際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為 O(logn)。
對(duì)數(shù)之間是可以互相轉(zhuǎn)換的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一個(gè)常量?；谖覀兦懊娴囊粋€(gè)理論：在采用大 O 標(biāo)記復(fù)雜度的時(shí)候，可以忽略系數(shù)，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在對(duì)數(shù)階時(shí)間復(fù)雜度的表示方法里，我們忽略對(duì)數(shù)的“底”，統(tǒng)一表示為 O(logn)。
- O(m+n)、O(m*n)
這個(gè)代碼的復(fù)雜度是由兩個(gè)數(shù)據(jù)的規(guī)模來(lái)決定的。
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;
}
上面這個(gè)例子， m 和 n 是表示兩個(gè)數(shù)據(jù)規(guī)模，我們不知道兩個(gè)誰(shuí)的量級(jí)更大，所以就是 ：T1(m)*T2(n) = O(f(m) * f(n))。
上面的例子是這里其實(shí)我沒太理解，不過我感覺我應(yīng)該用不到這么復(fù)雜的，就先不追究了
空間復(fù)雜度分析
其實(shí)空間復(fù)雜度分析和時(shí)間復(fù)雜度分析很類似?？聪旅娴睦?/p>
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
在這個(gè)例子里面，首先我們申請(qǐng)了一個(gè) i 的空間變量, 他是常量階的，和數(shù)據(jù)規(guī)模n 沒有關(guān)系，在for 里面，申請(qǐng)了一個(gè)n 長(zhǎng)度的數(shù)組。所以整個(gè)代碼的空間復(fù)雜度是O（n)
我們常見的空間復(fù)雜度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 這樣的對(duì)數(shù)階復(fù)雜度平時(shí)都用不到。
所以我暫時(shí)按照時(shí)間復(fù)雜度分析 的規(guī)律來(lái)理解空間復(fù)雜度，應(yīng)該沒有什么問題吧。
課后思考
有人說(shuō)，我們項(xiàng)目之前都會(huì)進(jìn)行性能測(cè)試，再做代碼的時(shí)間復(fù)雜度、空間復(fù)雜度分析，是不是多此一舉呢？而且，每段代碼都分析一下時(shí)間復(fù)雜度、空間復(fù)雜度，是不是很浪費(fèi)時(shí)間呢？你怎么看待這個(gè)問題呢？
針對(duì)這個(gè)問題，其實(shí)從我個(gè)人而言，我粗淺的理解為： 對(duì)代碼進(jìn)行分析，就會(huì)和host 沒有關(guān)系，對(duì)代碼進(jìn)行性能測(cè)試的話，可能受瀏覽器的內(nèi)核，版本等等之類的影響。還有一個(gè)先后順序的問題，但是實(shí)際上在工作中，普通的項(xiàng)目，做了其一應(yīng)該就ok 了吧。
