作為一個文科生轉(zhuǎn)行過來的程序媛，數(shù)據(jù)結(jié)構(gòu)和算法的概念對我來說都是很難茴晋。雖然平時工作幾乎很少用到算法道媚，但是我總覺得如果不懂?dāng)?shù)據(jù)結(jié)構(gòu)扁掸，在工作里面翘县，我?guī)缀醪粫タ紤]業(yè)務(wù)之外的東西，比如性能谴分，比如操作數(shù)組的時候锈麸，什么方法是最優(yōu)的，這些都是隱藏需求牺蹄。是我需要去突破的地方掐隐。
所以我決定硬著頭皮啃一下試試。（主要還是跟著老師學(xué)钞馁，能不能學(xué)懂我沒有太多信心虑省，但是我希望我可以）
那從今天就進(jìn)入數(shù)據(jù)結(jié)構(gòu)和算法的美妙世界吧！
目的
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法本身需要解決什么問題僧凰？
“快” 和“省”! 讓代碼運行更快探颈，讓我的代碼更優(yōu)雅，更節(jié)省存儲空間训措。
雞血??
我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法伪节，并不是為了死記硬背幾個知識點。我們的目的是建立時間復(fù)雜度绩鸣、空間復(fù)雜度意識怀大，寫出高質(zhì)量的代碼，能夠設(shè)計基礎(chǔ)架構(gòu)呀闻，提升編程技能化借，訓(xùn)練邏輯思維，積攢人生經(jīng)驗捡多，以此獲得工作回報蓖康，實現(xiàn)你的價值，完善你的人生垒手。
我被開篇的雞血給打醒了蒜焊， 哈哈哈哈
第一課，我學(xué)到的知識
- 學(xué)習(xí)復(fù)雜度分析的好處
老師講了很多關(guān)于復(fù)雜度分析的好處科贬，和事后統(tǒng)計法的區(qū)別泳梆。但是我個人粗淺的理解是：不用事后統(tǒng)計，在寫代碼的時候就考慮自己寫的代碼的時間,空間復(fù)雜度榜掌，就能有效粗略估計算法的執(zhí)行效率优妙，事先的預(yù)防成本肯定是低于代碼寫好以后再來優(yōu)化的成本的。
- 大O 復(fù)雜度表示法
從CPU 的角度來看唐责，代碼的執(zhí)行都是重復(fù)著：讀數(shù)據(jù)-運算-寫數(shù)據(jù) 的步驟鳞溉。當(dāng)我們寫出來的每一段代碼，如何“肉眼”估算他的計算時間呢鼠哥？
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
上面這個例子熟菲。for 循環(huán)之外的代碼都是運行一次看政，for 循環(huá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;
}
}
}
這次的代碼里面有兩個for 循環(huán)抄罕，還是嵌套的for 循環(huán)允蚣，那么第一個for 循環(huán)的運行次數(shù)是n ，第二個是n2
重要點：
所有的代碼執(zhí)行時間T(n） 和每行代碼的執(zhí)行次數(shù)n 成正比 總結(jié)成公式就是
T(n) = o(f(n))
這就是大 O 時間復(fù)雜度表示法呆贿。大 O 時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行時間嚷兔，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以做入，也叫作漸進(jìn)時間復(fù)雜度（asymptotic time complexity）冒晰，簡稱時間復(fù)雜度。
時間復(fù)雜度分析
- 只關(guān)注代碼里面循環(huán)次數(shù)最多的一段代碼竟块，并且排除掉常量壶运，低階, 系數(shù)。
這個道理還是很好理解的吧浪秘，因為影響代碼運行的最長時間蒋情，就是最復(fù)雜的那個。那些常量不管是多大耸携，他都只會執(zhí)行一次而已棵癣，無法對漸進(jìn)時間復(fù)雜度產(chǎn)生影響， - 加法法則
- 乘法法則： 嵌套代碼的復(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;
}
這樣的嵌套循環(huán)里夺衍，整個 cal() 函數(shù)的時間復(fù)雜度就是狈谊，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。
貼一個老師總結(jié)的復(fù)雜度量級
對于以上的幾種復(fù)雜度刷后，我來談一下我自己的理解
O(1)
代碼只會執(zhí)行一次的畴，是復(fù)雜度最低的渊抄，一般來說尝胆，只要代碼里不存在循環(huán)語句，遞歸語句护桦，正常的代碼執(zhí)行含衔，不管多少行，他的復(fù)雜度都是O(1)O(logn)二庵、O(nlogn)
一般的循環(huán)贪染，都可以歸為這種的復(fù)雜度里面, 這里再次套用一下老師的一個例子
i=1;
while (i <= n) {
i = i * 2;
}
這個例子里面，變量i 從1開始催享，每循環(huán)一次就乘以2杭隙，大于n 的時候才結(jié)束。
老師說這里是高中數(shù)學(xué)里面的等比數(shù)列因妙。我就恍然大悟痰憎，然后再去復(fù)習(xí)了一下等比數(shù)列和對數(shù)票髓。
這里代碼的復(fù)雜度是 x=log2n 實際上，不管是以 2 為底铣耘、以 3 為底洽沟，還是以 10 為底，我們可以把所有對數(shù)階的時間復(fù)雜度都記為 O(logn)蜗细。
對數(shù)之間是可以互相轉(zhuǎn)換的裆操，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)炉媒，其中 C=log32 是一個常量踪区。基于我們前面的一個理論：在采用大 O 標(biāo)記復(fù)雜度的時候吊骤，可以忽略系數(shù)朽缴，即 O(Cf(n)) = O(f(n))。所以水援，O(log2n) 就等于 O(log3n)密强。因此，在對數(shù)階時間復(fù)雜度的表示方法里蜗元，我們忽略對數(shù)的“底”或渤，統(tǒng)一表示為 O(logn)。
- O(m+n)奕扣、O(m*n)
這個代碼的復(fù)雜度是由兩個數(shù)據(jù)的規(guī)模來決定的薪鹦。
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 是表示兩個數(shù)據(jù)規(guī)模惯豆，我們不知道兩個誰的量級更大池磁，所以就是 ：T1(m)*T2(n) = O(f(m) * f(n))。
上面的例子是這里其實我沒太理解楷兽，不過我感覺我應(yīng)該用不到這么復(fù)雜的地熄，就先不追究了
空間復(fù)雜度分析
其實空間復(fù)雜度分析和時間復(fù)雜度分析很類似⌒旧保看下面的例子
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]
}
}
在這個例子里面端考，首先我們申請了一個 i 的空間變量, 他是常量階的，和數(shù)據(jù)規(guī)模n 沒有關(guān)系揭厚，在for 里面却特，申請了一個n 長度的數(shù)組。所以整個代碼的空間復(fù)雜度是O（n)
我們常見的空間復(fù)雜度就是 O(1)筛圆、O(n)裂明、O(n2 )，像 O(logn)太援、O(nlogn) 這樣的對數(shù)階復(fù)雜度平時都用不到闽晦。
所以我暫時按照時間復(fù)雜度分析 的規(guī)律來理解空間復(fù)雜度轰绵，應(yīng)該沒有什么問題吧。
課后思考
有人說尼荆，我們項目之前都會進(jìn)行性能測試左腔，再做代碼的時間復(fù)雜度、空間復(fù)雜度分析捅儒，是不是多此一舉呢液样？而且，每段代碼都分析一下時間復(fù)雜度巧还、空間復(fù)雜度鞭莽，是不是很浪費時間呢？你怎么看待這個問題呢麸祷？
針對這個問題澎怒，其實從我個人而言，我粗淺的理解為： 對代碼進(jìn)行分析阶牍，就會和host 沒有關(guān)系喷面，對代碼進(jìn)行性能測試的話，可能受瀏覽器的內(nèi)核走孽，版本等等之類的影響惧辈。還有一個先后順序的問題，但是實際上在工作中磕瓷，普通的項目盒齿，做了其一應(yīng)該就ok 了吧。
