先說結論
程式=資料結構+演算法
說的直接一點就是程式設計和演算法刷題這兩個東西要結合著用
寫在前面
資料結構和演算法是每一個學計算機同學的內功和心法
無論未來從事什么崗位這兩門課都繞不過去
甚至演算法這門課對不學計算機的同學也同樣重要
筆者在本科的時候只有資料結構這門課程，沒有演算法，筆者到大三的寒假參加藍橋杯比賽才剛剛知道有演算法這門課
但是筆者在備賽的時候時間倉促，沒有時間去系統地學習演算法
大概掌握得相對的程度也只有暴力演算法，字串專題，DFS，簡單的貪心演算法這四種技能
其實這個時候雙非和985的區別就體現出來了
資料結構最好建立在有一定離散數學的底子的基礎上，筆者學校的課程安排的不盡合理
資料結構在大二上學期就學了，但是離散數學到大二下才開始學
最重要的演算法課筆者的學校更是開都沒開，大概到筆者畢業的時候才剛剛開這門課
可惜開的太晚了，筆者此時已經沒有時間去蹭課了
所以最重要的兩門課在筆者的大學教的殘缺不全
因此很長時間都云里霧里的，但是如果搞不清楚這個問題，我們就沒有辦法很好地去LeetCode網站刷題
這兩門課筆者研究了很久，發現有些書名寫著資料結構，但里面卻有少許演算法，但也有些書名寫著演算法，里面也有少許資料結構
當然更多的書是將這兩門課并到一起來學習的，但實際上似乎乍看之下又沒什么聯系
概念
因此我們首先來看看這兩門課到底是個什么東西
資料結構
資料結構其實只有三個內容：線性結構、樹和圖
很多同學可能會問為什么會只有這三個部分
我們先來看看資料結構的概念
我們借用一下考研大綱的概念【因為教育部發布的比較權威】
資料結構：相互之間存在一種或多種特定關系的資料元素的集合
發現沒有，資料結構是一個集合，這個集合里是什么東西？
是資料元素之間的特定關系
那么既然是特定關系無非是三種：一對一，一對多，多對多
其實正好對應了三個部分
線性結構【一對一】
樹型結構【一對多】
圖型結構【多對多】
好，我們再拿生活當中的例子來舉例
案例一：
小張攢錢買了車，可是他家住在胡同的盡頭，胡同很窄，只能通過一輛車，而且是死胡同，小張每天都為停車發愁，如果回家早了停在里面，早上上班就要讓所有的人挪車，先讓胡同口那輛出去，然后挨著一輛一輛出去，這樣小張才能去上班，沒辦法，小張下班也不敢早回家了，等天黑了別的車都停進去了，再回去把車停在胡同口，這樣早上就可以第一個去上班了，就這樣，小張過起了“起早貪黑”的有車生活，
胡同很窄，只能通過一輛車， 而且是死胡同，所以只能從胡同口進出，小汽車呈線性排列，只能從一端進出，后進的汽車先出去
同學們發現沒有這是什么東西？
這是典型的資料結構里面的堆疊
案例二：家譜
這個就更直觀了，典型的樹結構，事實上樹形結構里的很多概念都是和家譜相似的
案例三：旅行地圖
圖形結構就不多做解釋啦，相信大家已經可以舉一反三了
同學們發現沒有，資料結構的作用是干嘛，就是把我們生活中的各種復雜的現象用比較直觀的關系圖給我們描繪出來
說的比較功利一點，我們在刷題的時候如果搞不清楚題目里所說的各種關系，我們應當先用資料結構將它們表示出來
演算法
關于演算法其實并沒有給出一個比較公認的定義，但是對它的含義是有一個基本的共識的
演算法是一系列解決問題的明確指令，也就是說，對于符合一定規范的輸入，能夠在有限時間內獲得要求的輸出，
其實言下之意，只要能通過一系列步驟解決某種問題的都叫演算法
演算法本身并不是一個答案，但是用演算法可以得到我們想要的答案
筆者一開始以為所有的演算法已經被窮盡了，其實不是
演算法是永遠不可能被窮盡的，因為生活中的問題是永遠解決不完的，因此筆者在置頂博客里也告訴大家
編程能力的強弱并不是在技術而是在創意
所以很多同學在刷演算法題的時候往往一下子沒思路就想著去看參考答案
實際上這個做法是錯誤的，演算法沒有正確與錯誤一說，只有優與劣一說
事實上只要給你足夠的時間，你可以用暴力演算法【所謂的蠻干】解決世界上絕大多數的問題
只是暴力演算法往往太慢了我們往往才另辟蹊徑
情景設計
假設我們是職業小偷，背包出門偷東西
我們假設背包的承受重量是4kg
擺在我們面前的有三種商品
A.音響【3000元，4kg】
B.筆記本電腦【2000元，3kg】
C.吉他【1500元，1kg】
當然小孩子才做選擇，成年人選擇全都要【開個玩笑】
由于我們的背包空間是有限的，所以只能選擇偷最高價值的商品
最簡單的都是把所有的可能性都列出來
【1】放棄偷竊【0元，0kg】
【2】偷吉他【C】【1500元，1kg】
【3】偷音響【A】【3000元，4kg】
【4】筆記本電腦【B】【2000元，3kg】
【5】偷吉他和音響【CA】【裝不下】
【6】偷吉他和筆記本電腦【CB】【3500元，4kg】
【7】偷音響和筆記本電腦【AB】【裝不下】
【8】全部偷走【ABC】【裝不下】
這樣雖然可行，但是速度太慢了，等我們考慮完，估計警察已經在背后站半天了
放到演算法時間復雜度大約是
，簡直慢如蝸牛
這個時候就要引出演算法中的動態規劃
我們先來看看動態規劃演算法的作業原理
動態規劃簡單地說就是先解決子問題，再解決母問題
當然這個概念比較難理解，請同學們慢慢看
我們回到剛才的問題
網格的各行為商品，各列為不同容量( 1~4kg)的背包，所有這些列你都需要，因為它們將幫助你計算子背包的價值，
首先來看第一行，意味著我們要嘗試偷吉他【但是到底偷不偷不一定，別忘了初心，我們是為了偷走最高價值的商品】
第一個單元格表示背包的容量為一kg，
吉他的重量也是一kg，這意味著可以裝入背包
這個單元格包含吉他，價值為1500美元
與這個單元格一樣，每個單元格表示背包的容量為2kg，可以裝下吉他
同學們可能對這個表格云里霧里，但是這里是假設只有吉他可以偷
這里同學們肯定會認為我在搞什么無聊的事情
但別忘了，我們之前說過
動態規劃簡單地說就是先解決子問題，再解決母問題
當前這張圖是表示，如果有一個容量4kg的背包，可在其中裝入的商品的最大價值為1500美元
當然肯定這不是最終的答案
接下來我們放入音響
在每一行可偷得商品都為當前行的商品以及之前各行的商品
這表示我們現在只能偷影響和吉他
第一行第一串列示
背包容量為1kg時，之前可裝入商品的最大價值
第二行第一串列示
我們要用1kg的背包，在同時能偷吉他和音響的情況下，現在可裝入的商品的最大價值
我們得出的結論是背包的容量只有1kg的時候，我們偷不了音響
所以這時候我們能偷的最貴東西仍然是1500元
后面的結論是一樣的
到第二行第四列的時候，我們發現背包容量為4kg的時候
最大的價值更新為3000元
最后我們加入筆記本電腦
但是這時候問題來了
背包容量為3kg的時候，我們可以偷的東西選擇性變大了，我們可以放棄吉他而去偷筆記本電腦，所以最大的價值更新為2000元
總算來到了最后的問題
對于容量為4kg的背包，情況很有趣
這是非常重要的部分
當前最大價值為3000元，你可以不偷音響，而偷筆記本電腦，但只價值2000元
那我們勢必面臨一個問題
3000元的音響 VS 2000元的筆記本電腦+1kg的空余容量
同學們發現沒有，之前在1kg的容量中我們可加入的最大價值是多少？
答案是1500元
這個時候就可以作比較了
3000元【音響】 VS 2000元【筆記本電腦】+1500元【吉他】
同學們現在是否明白了為什么要計算小背包可裝入了商品的最大價值
這樣余下的空間我們不必再花大量的時間去做計算
答案如下，將吉他和筆記本電腦裝入背包時價值最高，為3500美元
同學們聽到這里可能還是有點疑惑，其實每個單元格的價值，使用的公式都相同
cell[i][j]=上一個單元的價值cell[i-1][j]VS當前商品的價值+剩余空間的價值
你可以使用這個公式來計算每個單元格的價值,最終的網格將與前一個網格相同，
現在你明白了為何要求解子問題吧?你可以合并兩個子問題的解來得到更大問題的解，
想必同學們聽到這里應該明白了吧，演算法其實是為了幫我們更快地解決問題才用的東西【當然別演算法去偷東西哈，違反亂紀的事情咱們不能干】
并且老祖宗也告訴過我們，辦法總比問題多
所以沒有哪個問題只有一個辦法解決，只有巧辦法和笨辦法
演算法與資料結構的應用
那肯定很多同學要問了，這兩個單獨拿出來我明白了，但是有什么關系呢
好，我們拿資料結構中的案例三來繼續說明
假設筆者要和一個漂亮妹妹去約會，筆者已經計劃好了去這六個地方
但是呢漫長的路程不僅會耗費大量的路費，同時也會浪費很多時間在來回奔波的路上
筆者的預算和體力都比較有限，如果耗費太多所有的計劃就都泡湯了
因此筆者勢必要規劃出一條最短的路程，這樣筆者就能有足夠的時間撩妹
事實上恰恰對應了演算法中的最短路徑演算法【關于最短路徑演算法筆者在以后的博客里再和大家詳細討論】
同學們發現沒有，筆者是在用最短路徑演算法之前已經無形中干了一件什么事情
沒錯，筆者已經構建好了一張圖，在這個基礎上才能規劃路線
因此往往在演算法之前，將每個現實生活中的一切轉換成對應的資料結構就顯得尤其重要
總結
只有資料結構沒有演算法，相當于只把資料存盤到計算機中，而沒有有效的方法去處理，就像一幢只有框架的爛尾樓
若只有演算法，沒有資料結構，就像沙漠里的海市蜃樓，只不過是空中樓閣罷了，
我們往往面對一個生活實際問題的時候先用資料結構去構建模型，再用演算法在這個模型上進行一系列的操作，從而使其出現我們想要的結果
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/451340.html
標籤：其他