5.數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系
1.常見數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)其實(shí)逃離不了數(shù)據(jù)答毫，數(shù)據(jù)結(jié)構(gòu)發(fā)明的本身是為了更好的處理數(shù)據(jù)。其實(shí)季春，數(shù)據(jù)結(jié)構(gòu)按照在內(nèi)存里的分布總共分兩類烙常，線性和非線性。我們?cè)诜蔷€性結(jié)構(gòu)上處理數(shù)據(jù)鹤盒，都是為了更好的達(dá)到我們想要的性能蚕脏。
按在內(nèi)存中是否是線性結(jié)構(gòu)分：
- 線性結(jié)構(gòu)：對(duì)應(yīng)數(shù)組,下標(biāo)訪問O(1),排序最快O(nlogn),也有O(n).這是最直觀的一個(gè)結(jié)構(gòu)。
- 非線性結(jié)構(gòu)：鏈表侦锯，樹驼鞭，圖，其中尺碰，鏈表結(jié)構(gòu)其實(shí)可以認(rèn)為是樹和圖的基礎(chǔ)結(jié)構(gòu)挣棕，而圖又是樹結(jié)構(gòu)的一個(gè)特例。
按不同的使用規(guī)則分：
- 棧亲桥，后進(jìn)先出的規(guī)則洛心，有一定順序的，一般用線性結(jié)構(gòu)實(shí)現(xiàn)题篷。
- 隊(duì)列词身，先進(jìn)先出的規(guī)則，可以用線性結(jié)構(gòu)實(shí)現(xiàn)番枚，也可以用非線性結(jié)構(gòu)實(shí)現(xiàn)法严。無論哪個(gè)結(jié)構(gòu)损敷，都需要保留兩個(gè)標(biāo)記，頭深啤，尾拗馒。頭部負(fù)責(zé)出隊(duì)列，尾部負(fù)責(zé)進(jìn)隊(duì)列溯街。
- 堆诱桂，有一定規(guī)則的樹結(jié)構(gòu)，保證頂點(diǎn)是最大或者最小來稱為大頂堆或者小頂堆呈昔。
- 圖挥等，抽象上比樹結(jié)構(gòu)多一些指向指針的結(jié)構(gòu)，可以用部分線性部分非線性結(jié)構(gòu)來組合表示韩肝，一般根據(jù)所需要表示圖的特性來決定触菜。
- 哈希表，這是一種線性表和鏈表結(jié)合的數(shù)據(jù)結(jié)構(gòu)哀峻，意圖在使用索引值快速的進(jìn)行查找涡相，一種用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。
2.基本的數(shù)據(jù)結(jié)構(gòu)算法
說到基礎(chǔ)：我能想到的就兩個(gè)剩蟀，查找和排序催蝗。當(dāng)然，不是說其他不是基礎(chǔ)育特，只是我看來丙号，這兩個(gè)是很多問題的基礎(chǔ)思路，并加以一定規(guī)律的擴(kuò)展缰冤。
- 查找：
假定我們有N個(gè)線性結(jié)構(gòu)的數(shù)據(jù)犬缨，我們要在N個(gè)數(shù)據(jù)中查找某個(gè)給定值。
常規(guī)的查找棉浸，我們要把整個(gè)數(shù)組走一遍怀薛，時(shí)間復(fù)雜度一般為O(N)
但是如果遇到特殊情況：
1.我們的數(shù)組是按一定規(guī)則（從小到大，從大到小迷郑，或者排好序的數(shù)組在某個(gè)節(jié)點(diǎn)旋轉(zhuǎn)過一次且只有一次）的時(shí)候枝恋，我們可以用 二分查找 法來做，這會(huì)讓平均的時(shí)間復(fù)雜度降為O(logN)
2.我們要查找的是數(shù)據(jù)中m個(gè)最大或者最小的元素嗡害，這個(gè)時(shí)候焚碌，我們可以借助堆結(jié)構(gòu)。
對(duì)于非線性結(jié)構(gòu)霸妹，比如說樹十电，查找某個(gè)值，或者某幾個(gè)節(jié)點(diǎn)的最大最小值，我們一般用動(dòng)態(tài)規(guī)劃或者分治（迭代實(shí)現(xiàn)）摆出。
- 排序
常見排序算法的時(shí)間復(fù)雜度為O()和O(NlogN),當(dāng)然也有一些高級(jí)的排序算法只要O(N)或O(N+K).例如python中給出的sort()用的是Timsort朗徊，時(shí)間復(fù)雜度為O(NlogN),兼用了二分插入排序和歸并排序首妖。
排序里的算法沒有好壞偎漫，只有說在什么場(chǎng)合的使用。（具體排序算法有缆，會(huì)在數(shù)據(jù)結(jié)構(gòu)和算法里講象踊。）
其實(shí)我們想到的這兩個(gè)算法是最基本的數(shù)據(jù)結(jié)構(gòu)算法，高級(jí)的一些算法棚壁，能分治用動(dòng)態(tài)規(guī)劃的杯矩，只要找出那個(gè)基本公式使用迭代就可以解決，但是想不到的話袖外，可能會(huì)麻煩點(diǎn)史隆。尋找問題里的重復(fù)點(diǎn)，這是解決問題的一種思路曼验，找意圖泌射，找到題目沒有明說，但其實(shí)是存在的一種規(guī)律鬓照。這是題外話熔酷。
2.總結(jié)
不知道拋磚引玉說了那么多，是否點(diǎn)了重點(diǎn)豺裆。
其實(shí)重點(diǎn)是拒秘，我們要熟悉數(shù)據(jù)結(jié)構(gòu)和算法的使用場(chǎng)合和分情況討論。就像基礎(chǔ)的排序算法臭猜，插入排序躺酒，數(shù)組和鏈表結(jié)構(gòu)都可以實(shí)現(xiàn)，但是根據(jù)需要來選擇用數(shù)組還是鏈表蔑歌，根據(jù)需要來選擇是用哪種排序方法羹应。
很多時(shí)候，光看數(shù)據(jù)結(jié)構(gòu)和算法本身丐膝，并不能加深我們對(duì)其的印象量愧，需要聯(lián)系實(shí)際中的一些情況來看，沒有現(xiàn)成的帅矗，去發(fā)現(xiàn)和尋找偎肃，然后你會(huì)發(fā)現(xiàn)，發(fā)現(xiàn)和思索多了浑此，你的思維就會(huì)跟上去了累颂。
沒有最好的，只有最適合的，有時(shí)候紊馏，我們選擇了一種看似特別好的算法料饥，可能會(huì)在某種特殊情況下性能下降很厲害，這種時(shí)候朱监，我們就需要考慮這種特殊情況是否在我們的數(shù)據(jù)中出現(xiàn)的多岸啡，如果多，我們需要換一種可能不是最好赫编，但是綜合起來的性能還不錯(cuò)的算法巡蘸。
畢竟很多時(shí)候，雙刃劍就是擂送，一個(gè)事物的優(yōu)點(diǎn)悦荒，往往也是它的弱點(diǎn)，你不僅要清楚其優(yōu)點(diǎn)所在環(huán)境嘹吨，更要清楚其弱點(diǎn)產(chǎn)生的環(huán)境搬味。這樣在學(xué)習(xí)的時(shí)候會(huì)有所留意，日后用的時(shí)候也會(huì)權(quán)衡的得心應(yīng)手蟀拷。
給定的數(shù)據(jù)情況決定我們所采用的數(shù)據(jù)結(jié)構(gòu)碰纬，具體要達(dá)成的目標(biāo)和性能，決定我們采用的算法匹厘。當(dāng)多種數(shù)據(jù)結(jié)構(gòu)和算法可選擇時(shí)嘀趟，選擇最合適的。也可以給不同的場(chǎng)景選擇不同的愈诚。
以上就是我對(duì)算法入門的一些認(rèn)識(shí)她按，深入部分尚為涉及，一點(diǎn)個(gè)人看算法的感受炕柔，拋磚引玉酌泰，個(gè)別深入細(xì)節(jié)，會(huì)另開章節(jié)匕累。
