這是數(shù)據(jù)結(jié)構(gòu)系列文章的第一篇峡谊，這是文章的列表恤煞。
注：想要學(xué)好數(shù)據(jù)結(jié)構(gòu)趾撵，掌握至少一門(mén)語(yǔ)言是必需的侄柔，這樣才能將學(xué)到的數(shù)據(jù)結(jié)構(gòu)知識(shí)加以鞏固。
文章目錄
- 語(yǔ)言以及代碼書(shū)寫(xiě)規(guī)范
- 時(shí)間復(fù)雜度和空間復(fù)雜度分析
- 數(shù)據(jù)結(jié)構(gòu)與算法中的一些概念
1. 語(yǔ)言以及代碼書(shū)寫(xiě)規(guī)范
- 語(yǔ)言其實(shí)無(wú)所謂占调，重點(diǎn)在于數(shù)據(jù)結(jié)構(gòu)的知識(shí)暂题。不同語(yǔ)言實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)算法，其實(shí)大同小異究珊。在教科書(shū)中薪者，常用的語(yǔ)言有
C/C++ 和 java兩種。
- 這兩種語(yǔ)言在在數(shù)據(jù)結(jié)構(gòu)與算法上剿涮，轉(zhuǎn)化起來(lái)其實(shí)很簡(jiǎn)單言津，所以以后的文章攻人，可能會(huì)用到這兩種語(yǔ)言。
- 代碼書(shū)寫(xiě)規(guī)范：
- 程序中用到的某些常量或者調(diào)用的函數(shù)等可以用加注釋的方式悬槽，省略其定義怀吻。
- include語(yǔ)句可不寫(xiě)
- 測(cè)試代碼可不寫(xiě)
- 數(shù)據(jù)類型上，int初婆， char及其數(shù)組類型蓬坡，指針類型即可覆蓋大部分
2. 時(shí)間復(fù)雜度和空間復(fù)雜度分析
- 其實(shí)對(duì)于一些簡(jiǎn)單的程序，時(shí)間復(fù)雜度和空間復(fù)雜度是比較簡(jiǎn)單的磅叛，但是也有難的地方屑咳，特別是算法中涉及到遞歸等比較高級(jí)的特性時(shí)。時(shí)間復(fù)雜度的考察較多弊琴。
- 在考研中兆龙，時(shí)間復(fù)雜度的考察一般是考察排序算法中的復(fù)雜度，這只需要簡(jiǎn)單記憶或者理解記憶即可访雪。當(dāng)然详瑞，也不僅僅是這樣的掂林，也會(huì)給你一段程序臣缀，要你分析其復(fù)雜度，這就需要你有一定的分析能力了泻帮。
(1) 時(shí)間復(fù)雜度
1) 常用的時(shí)間復(fù)雜度比較關(guān)系（需要牢記）：
時(shí)間復(fù)雜度的比較關(guān)系.png
2) 實(shí)例分析
- 分析時(shí)間復(fù)雜度其實(shí)就是分析算法每個(gè)指令執(zhí)行的次數(shù)精置。而一般一行一行的代碼其實(shí)其執(zhí)行次數(shù)為常數(shù)，一般不考慮锣杂，所以一般要分析的地方在循環(huán)脂倦、遞歸等地方。
- 計(jì)算出執(zhí)行次數(shù)后元莫，一般是一個(gè)n的表達(dá)式赖阻，只需要提取式子中隨著n的變化而變化最快的那個(gè)部分文留，一般是在(1)中比較關(guān)系里的那些蹭越。
實(shí)例1：純循環(huán)的情況
這種情況只需要簡(jiǎn)單計(jì)算循環(huán)內(nèi)的指令執(zhí)行次數(shù)就行了。
實(shí)例1.png
以上代碼第一層是n次循環(huán)振劳，第二層是n - (i + 1) + 1 = n - i次循環(huán)茎截，而i是從0開(kāi)始到n - 1, 所以總的次數(shù)應(yīng)該是：
i = 0 時(shí)苇侵， target 運(yùn)行 n - 1 次
i = 1 時(shí)， target 運(yùn)行 n - 2 次
...
i = n - 1 時(shí)企锌，target 運(yùn)行 0 次
所以總共次數(shù) = (n - 1) + (n - 2) + (n - 3) + ... + 0
總共有n項(xiàng)榆浓，根據(jù)等差數(shù)列求和：sum = ((n-1) + 0) * n/ 2 = n(n-1) / 2
實(shí)例2：循環(huán)次數(shù)依賴循環(huán)內(nèi)數(shù)據(jù)變化的情況
有些題目中，循環(huán)的次數(shù)要依賴循環(huán)內(nèi)部變量的變化情況而定撕攒。
image.png
上述代碼只有一個(gè)while循環(huán)陡鹃，但是循環(huán)次數(shù)需要通過(guò)i和s計(jì)算, 1,2兩條指令會(huì)影響循環(huán)的跳出烘浦。并不是簡(jiǎn)單的自增1。
初始：i = 0, s = 0
i = 1, s += i = 1 // 1次
i = 2, s += i = 1 + 2 = 3 // 2次
i = 3, s += i = 1 + 2 + 3 = 6 // 3次
...
i = m, s += m = 1 + 2 + 3 + ... + m = m(m+1)/2 // m次
假設(shè)循環(huán)m次結(jié)束杉适，那么 s = m(m+1)/2 >= n
換一種表示方式：m(m+1)/2 + k = n谎倔， k為一個(gè)常數(shù)
則有：m*m + m + 2k -2n = 0
image.png
按照前面所說(shuō)取影響最大的一項(xiàng)做簡(jiǎn)化的規(guī)則，時(shí)間復(fù)雜度為：
image.png
實(shí)例3：遞歸的情況
image.png
遞歸的情況分析會(huì)比較難猿推，但是也有一般的套路片习。上面的代碼是歸并排序的關(guān)鍵代碼。merge函數(shù)的復(fù)雜度為
O(n)蹬叭。
-> 設(shè)因?yàn)閙erge的復(fù)雜度為O(n)藕咏，所以可以假設(shè)其操作次數(shù)為cn，再假設(shè)mergesort的操作次數(shù)為f(n).
-> 實(shí)例中的規(guī)模為：j - i + 1秽五，若調(diào)用mergesort(1, n)孽查， 那么規(guī)模就是n。
-> 一個(gè)規(guī)模為n的mergesort指令 = 兩個(gè)規(guī)模為n/2的mergesort指令 + cn
即：
image.png
假設(shè)最后的問(wèn)題
