你當前所在位置:首頁 > IT技術探討 > 學編程必看:這些算法你掌握了嗎?

學編程必看:這些算法你掌握了嗎?

許多初學軟件開發的同學,認為學開發就是學各種編程語言,或者認為能學到最新的編程語言、技術和標準就是最牛叉的。其實這種認知是有失偏頗的。

 

編程語言固然重要,但是計算機算法和理論更為重要,因為計算機編程語言和開發平臺更新迭代日新月異,但萬變不離其宗的是那些算法和理論。


算法1算法——程序員的內功

 

形象點比喻:

 

算法、數據結構、編譯原理、關系型數據庫原理和計算機體系結構等這些算法和理論知識體系屬于程序員的“內功”。

 

各種各樣五花八門的編程語言、技術和標準則更是“外功”。

 

只會追求最新語言,懂些花架子用來炫耀,卻沒有過硬內功的程序員,是不可能成為高手的。

 

算法內功高手

 

也許有人會問:“今天計算機這么快,算法還重要嗎?”

 

其實永遠不會有太快的計算機,因為我們總會想出新的應用。

 

在網絡時代,信息量越來越大,越來越多的挑戰需要靠卓越的算法來解決。

 

關于程序員是否必須懂算法的問題,IT圈流行的這樣兩張動圖足矣給出答案:

 

A、懂算法的程序員:


懂算法的程序員

 

B、不懂算法的程序員:

 

不懂算法的程序員


算法2如何學習算法?

 

一、看書

 

如果你是小白,你連常見的數據結構,如鏈表、樹以及常見的算法思想,如遞歸、枚舉、動態規劃這些都沒學過,那么,建議你先去找本書,先把最基礎的知識搞懂。

 

你需要搞懂的最基礎的知識包括:

 

1、常見數據結構:鏈表、樹(如二叉樹)。

2、常見算法思想:貪婪法、分治法、窮舉法、動態規劃,回溯法。

 

這里推薦一本能比較系統的學習算法的書籍:《算法導論》。

 04.jpg

 

這本書深入淺出,全面系統地介紹了計算機算法。對每一個算法的分析既易于理解又十分有趣,并保持了數學嚴謹性。

 

二、刷題

 

學習算法有沒有捷徑?如果說有,那么這個捷徑就是腳踏實地多動手去刷題,多刷題。

 

在做題的時候,我們要追求完美,要力求一題多解。千萬不要把一道題做出來之后,提交通過,然后就趕緊下一道。

 

如果自己實在想不出來其他辦法了,可以去看看別人是怎么做的,之后,遇到類似的題,你就會更有思路,更知道往哪個方向想。千萬不要覺得模仿別人的做法是件丟人的事。

 

可以從簡單暴力入手做一道題,在考慮空間與時間之間的衡量,一點點去優化。

 

道理不多說,趕緊舉個例題:

 

問題: 一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法?

 

▼方法一:暴力遞歸


算法-暴力遞歸


這個方法的時間復雜度很高,達到指數級別了。

 

▼方法二:空間換時間


算法-空間換時間

 

這個用空間換時間的方法可以大大縮短時間。

 

▼方法三:斐波那契數列


算法-斐波那契數列

 


這個方法可以把空間復雜度弄得更小,不需要HashMap來保存狀態。


算法3程序員必須掌握的五大基礎實用算法

 

算法一:快速排序

 

快速排序是由東尼·霍爾所發展的一種排序算法。

 

在平均狀況下,排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他Ο(n log n) 算法更快,因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。

 

快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。

 

算法二:堆排序算法

 

堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,并同時滿足堆積的性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。

 

堆排序的平均時間復雜度為Ο(nlogn) 。

 

算法三:歸并排序

 

歸并排序(Merge sort,臺灣譯作:合并排序)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。

 

算法四:二分查找算法

 

二分查找算法是一種在有序數組中查找某一特定元素的搜索算法。

 

搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜 素過程結束;如果某一特定元素大于或者小于中間元素,則在數組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。

 

如果在某一步驟數組 為空,則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半,時間復雜度為Ο(logn) 。

 

算法五:BFPRT(線性查找算法)

 

BFPRT算法解決的問題十分經典,即從某n個元素的序列中選出第k大(第k小)的元素,通過巧妙的分 析,BFPRT可以保證在最壞情況下仍為線性時間復雜度。該算法的思想與快速排序思想相似,當然,為使得算法在最壞情況下,依然能達到o(n)的時間復雜 度,五位算法作者做了精妙的處理。

 

算法圖


算法4結束語:

 

算法是程序員在追求高速度,高效率的路上不得不學的“內功”,而且算法幾乎是所有大廠技術面試的必考項目。學好算法和數據結構,無論是應對大廠面試,還是職業長遠規劃,甚至對自己的邏輯能力的提升,都有極大的幫助。

 

小伙伴們,如果你能耐心看到這里,并且能大概看懂本文的50%的內容,那么,恭喜你!你已經走在成為程序員的路上了,你可以選擇自學或參加職業培訓。

 

如果你看不太懂,但對這些感興趣,沒關系,可以找一家有資質的專業的針對零基礎的IT職業培訓學校,讓老師手把手教你從零學起。

課程預約

极速1分彩_Welcome