作為一名非科班出身的程序員，要修煉的內(nèi)功其實(shí)挺多的。現(xiàn)在就開(kāi)始記錄自己修煉數(shù)據(jù)結(jié)構(gòu)與算法的路程。
從數(shù)據(jù)結(jié)構(gòu)與算法的字面意義上面來(lái)看，一方面是數(shù)據(jù)結(jié)構(gòu)，另外一方面是算法。
一、算法
計(jì)算機(jī)處理信息的本質(zhì)還是在于算法。算法是獨(dú)立存在的一種解決問(wèn)題的方法和思想。對(duì)于算法而言，語(yǔ)言并不重要，重要的是思想，語(yǔ)言只是去實(shí)現(xiàn)一個(gè)算法的載體而已。在LeetCode上面，我們可以看到能夠刷題的語(yǔ)言有C、C++、Java、Python、Javascript等語(yǔ)言。
算法具有五個(gè)特性：
1、輸入: 算法具有0個(gè)或多個(gè)輸入
2、輸出: 算法至少有1個(gè)或多個(gè)輸出
3、有窮性: 算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無(wú)限循環(huán)，并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成
4、確定性：算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性
5、可行性：算法的每一步都是可行的，也就是說(shuō)每一步都能夠執(zhí)行有限的次數(shù)完成
時(shí)間復(fù)雜度和大"O"記法
常常我們會(huì)看到時(shí)間復(fù)雜度這概念，沒(méi)有接觸過(guò)數(shù)據(jù)結(jié)構(gòu)與算法的話，可能會(huì)誤以為是采用了代碼運(yùn)行的時(shí)間去衡量算法的有效性，但是這樣的觀念是不對(duì)的。因?yàn)橥环N代碼放到不同機(jī)器上去跑，得到結(jié)果所消耗的時(shí)間是不同的。但是我們換一種思路去看待這個(gè)問(wèn)題，同樣的代碼，他運(yùn)行的步驟肯定是相同的。即使在不同的機(jī)器上面，每一步運(yùn)行所消耗的時(shí)間是不同的，但是對(duì)于算法進(jìn)行多少個(gè)基本操作（即花費(fèi)多少時(shí)間單位）在規(guī)模數(shù)量級(jí)上卻是相同的，由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時(shí)間效率。
三種時(shí)間復(fù)雜度
在進(jìn)行算法時(shí)間復(fù)雜度分析的時(shí)候，存在如下幾種時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度：完成task最少需要的操作數(shù)。
- 平均時(shí)間復(fù)雜度：完成task平均需要的操作數(shù)。
- 最壞時(shí)間復(fù)雜度：完成task最多需要的操作數(shù)。
我們最為關(guān)注的就是最壞的情況，也就是最壞時(shí)間復(fù)雜度。然后我們?cè)谝恍┡判蛩惴ɡ锩婵梢钥吹剿鼈內(nèi)叻謩e的情況是什么。
常見(jiàn)的時(shí)間復(fù)雜度
我們需要記住這個(gè)時(shí)間復(fù)雜度的關(guān)系
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2) <O(n^3) <O(2^n) <O(n!)<O(n^n)
Python內(nèi)置類(lèi)型的性能分析
就列表而言
| 操作 | 時(shí)間復(fù)雜度 | 解釋 |
|---|---|---|
| index[n] | O(1) | 索引一步就取到了 |
| index assignment | O(1) | 采用索引的方式賦值 |
| append | O(1) | 尾部追加 |
| pop() | O(1) | 尾部給彈出一個(gè)元素 |
| pop(i) | O(n) | 最壞情況就是從頭部取 |
| insert(i, item) | O(n) | |
| del operator | O(n) | 代表了一個(gè)元素一個(gè)元素去刪除 |
| iteration | O(n) | 遍歷 |
| contains(in) | O(n) | 看元素是不是在list里面 |
| get slice[x:y] | O(k) | 定位到x為O(1)，一直取到y(tǒng)，跨度是k |
| del slice | O(n) | 中間元素給刪掉，那么后面的元素就需要向前移動(dòng)，補(bǔ)上空位置 |
| set slice | O(n+k) | 先是要?jiǎng)h除一部分元素，然后再補(bǔ)充上 |
| reverse() | O(n) | |
| concatenante | O(k) | 兩個(gè)列表相加，第二列表的元素為k個(gè) |
| sort | O(nlogn) | 封裝的sort |
| multiply | O(nk) | 一個(gè)列表可以去乘一個(gè)數(shù)，n是元素，k是個(gè)數(shù) |
dict內(nèi)置操作的時(shí)間復(fù)雜度
| 操作 | 時(shí)間復(fù)雜度 | 解釋 |
|---|---|---|
| copy | O(n) | 就是復(fù)制一份 |
| get item | O(1) | 通過(guò)鍵可以立馬拿到值 |
| set item | O(1) | |
| delete item | O(1) | |
| contains (in) | O(1) | |
| iteration | O(n) | 迭代肯定是O(n) |
二、數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)知識(shí)靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。Python里面內(nèi)置了挺多的數(shù)據(jù)結(jié)構(gòu)，例如列表、元組、字典等等。
程序 = 數(shù)據(jù)結(jié)構(gòu)+算法
三、時(shí)間復(fù)雜度實(shí)際分析
我們可以通過(guò)主定理來(lái)分析一下遞歸問(wèn)題里面的算法復(fù)雜度。
持續(xù)更新中...
數(shù)據(jù)結(jié)構(gòu)與算法系列博客：
一、數(shù)據(jù)結(jié)構(gòu)與算法概述
二、數(shù)組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊(duì)列（Stack and Queue
五、樹(shù)（Trees）
六、遞歸與回溯算法
七、動(dòng)態(tài)規(guī)劃
八、排序與搜索
九、哈希表
參考資料：
1、https://baike.baidu.com/item/%E4%B8%BB%E5%AE%9A%E7%90%86/3463232?fr=aladdin
