演算法之路該如何學習?

無任何演算法基礎,各位開始你的吐槽吧!本人大學狗一枚,由於某些原因想在演算法打下基礎,比別人先走一步才有領先不掛科的還有穩排名的基礎,說到這裡估計又快被打了


搬運工,看到一篇關於演算法學習之路的總結,希望對你有幫助。
原文鏈接:http://zh.lucida.me/blog/on-learning-algorithms/

我的演算法學習之路
MAY 4TH, 2014 | COMMENTS
關於

嚴格來說,本文題目應該是我的數據結構和演算法學習之路,但這個寫法實在太繞口——況且CS中的演算法往往暗指數據結構和演算法(例如演算法導論指的實際上是數據結構和演算法導論),所以我認為本文題目是合理的。

原文作者:Lucida

這篇文章講了什麼?

  1. 我這些年學習數據結構和演算法的總結。
  2. 一些不錯的演算法書籍和教程。
  3. 演算法的重要性。

初學

第一次接觸數據結構是在大二下學期的數據結構課程。然而這門課程並沒有讓我入門——當時自己正忙於倒賣各種MP3和耳機,對於這些課程根本就不屑一顧——反正最後考試劃個重點也能過,於是這門整個計算機專業本科最重要的課程就被傻逼的我直接忽略過去了。

直到大三我才反應過來以後還要找工作——而且大二的折騰證明了我並沒有什麼商業才能,以後還是得靠碼代碼混飯吃,我當時驚恐的發現自己對編程序幾乎一無所知,於是我給自己制訂了一個類似於建國初期五年計劃的讀書成長計劃,其中包括C語言基礎、數據結構以及計算機網路等方面的書籍。

讀書計劃的第一步是選擇書籍,我曾向當時我覺得很牛的」學長」和」大神」請教應該讀哪些演算法書籍,」學長」們均推薦演算法導論,還有幾個」大神」推薦計算機程序設計藝術(現在我疑心他們是否翻過這些書),草草的翻了下這兩本書發現實在看不懂,但幸運的是我在無意中發現了豆瓣這個神奇的網站,裡面有很多質量不錯的書評,於是我就把評價很高而且看上去不那麼嚇人的計算機書籍都買了下來——事實證明豆瓣要比這些」學長」或是」大神」靠譜的多得多。

數據結構與演算法分析——C語言描述

數據結構與演算法分析——C語言描述是我學習數據結構的第一本書:當時有很多地方看不懂,於是做記號反覆看;代碼看不明白,於是抄到本子上反覆研讀;一些演算法想不通,就把它所有的中間狀態全畫出來然後反覆推演。事實證明儘管這種學習方法看起來傻逼而且效率很低,但對於當時同樣傻逼的我卻效果不錯——傻人用傻辦法嘛,而且這本書的課後題大多都是經典的面試題目,以至於日後我看到編程之美的第一反應就是這貨的題目不全是抄別人的么。

至今記得,這本書為了說明演算法是多麼重要,在開篇就拿最大子序列和作為例子,一路把複雜度從O(N3)殺到O(N2)再到O(NlgN)最後到O(N),當時內心真的是景仰之情=如滔滔江水連綿不絕,尼瑪為何可以這麼屌,

此外,我當時還把這本書里圖演算法之前的數據結構全手打了一遍,後來找實習還頗為自得的把這件事放到簡歷里,現在想想真是傻逼無極限。

憑藉這個讀書成長計劃中學到的知識,我總算比較順利的找到了一份實習工作,這是後話。

入門

我的實習並沒有用到什麼演算法(現在看來就是不停的堆砌已有的API,編寫一堆自己都不知道對不對的代碼而已),在發現身邊的人工作了幾年卻還在和我做同樣的事情之後,我開始越來越不安。儘管當時我對自己沒什麼規劃,但我清楚這絕壁不是我想做的工作。

微軟的夢工廠

在這個搖擺不定的時刻,微軟的夢工場成了壓倒駱駝的最後一支稻草,這本書對微軟亞洲研究院的描寫讓我下定了」找工作就要這樣的公司」的決心,然而我又悲觀的發現無論是以我當時的能力還是文憑,都無法達到微軟亞研院的要求,矛盾之下,我徹底推翻了自己」畢業就工作」的想法,辭掉實習,準備考研。

考研的細節無需贅述,但至今仍清楚的記得自己在複試時驚奇且激動的發現北航宿舍對面就是微軟西格瑪大廈,那種離理想又進了一步的感覺簡直爽到爆。

演算法設計與分析

我的研究生生涯絕對是一個反面典型——翹課,實習,寫水論文,做水研究,但有一點我頗為自得——從頭到尾認真聽了韓軍教授的演算法設計與分析課程。

韓軍給我印象最深的有兩點:課堂休息時跑到外面和幾個學生借火抽煙;講解演算法時的犀利和毫不含糊。

儘管韓軍從來沒有主動提及,但我敢肯定演算法設計與分析基礎就是他演算法課程事實上的(de-facto)教材,因為他的課程結構幾乎和這本書的組織結構一模一樣。

如果數據結構與演算法分析——C語言描述是我的數據結構啟蒙,那麼韓軍的課程和演算法設計與分析基礎就是我的演算法啟蒙,結合課程和書籍,我一一理解並掌握了複雜度分析、分治、減治、變治、動態規劃和回溯這些簡單但強大的演算法工具。

演算法引論

演算法引論是我這時無意中讀到的另一本演算法書,和普通的演算法書不同,這本書從創造性的角度出發——如果說演算法導論講的是有哪些演算法,那麼演算法引論講的就是如何創造演算法。結合前面的演算法設計與分析基礎,這本書把我能解決的演算法問題數量擴大了一個數量級。

之後,在機緣巧合下,我進入微軟亞洲工程院實習,離理想又近了一步,自我感覺無限牛逼。

鞏固

在微軟工程院的實習是我研究生階段的一個非常非常非常重要的轉折點:

1.做出了一個還說的過去的小項目。
2.期間百度實習面試受挫,痛定思痛之下閱讀了大量的程序設計書。
3.微軟的實習經歷成為了我之後簡歷上為數不多的亮點之一(本屌一沒成績,二沒論文,三沒ACM)。
這裡就不說1和3了(和本文題目不搭邊),重點說說2。

由於當時組內沒有特別多的項目,我負責的那一小塊又提前搞定了,mentor便很慷慨的扔給我一個Kinect和一部Windows Phone讓我研究,研究嘛,自然就沒有什麼deadline,於是我就很雞賊的把時間三七開:七分倒騰Windows Phone,三分看書經典論文。

然而一件事打斷了這段安逸的生活——

百度實習面試

基友在人人發百度實習內推貼,當時自我感覺牛逼閃閃放光芒,於是就抱著看看國內IT環境+虐虐面試官的變態心理投了簡歷,結果在第一面就自己的師兄爆出翔:他讓我寫一個stof(字元串轉浮點數),我磨磨唧唧半天也沒寫出完整實現,之後回到宿舍趕快寫了一個版本發到師兄的郵箱,結果對方壓根沒鳥我。

這件事對我產生了很大的震動——

  • 原來自己連百度實習面試都過不去。
  • 原來自己還是一個編程弱逼。
  • 原來自己還是一個演算法菜逼。

痛定思痛,我開始了第二個」五年計劃」,三七開的時間分配變成了七三開:七分看書,三分WP。而這一階段的重點從原理(Principle)變成了實現(Implementation)——Talk is cheap, show me the code.

Elements of Programming

由於一直覺得名字裡帶」Elements of」的都是酷炫叼炸天的書,所以我幾乎是毫不猶豫的買了這本Elements of Programming,事實上這本書里的代碼(或者說STL的代碼)確實是:快,狠,准,古龍高手三要素全齊。

C Interfaces and Implementation

百度面試被爆出翔的經歷讓我意識到另一個問題,絕大多數公司面試時都需要在紙上寫C代碼,而我自己卻很少用C(多數情況用C#),考慮到自己還沒牛逼到能讓公司改變面試流程的地步,我需要提升自己編寫C代碼的能力(哪怕只是為了面試)。一頓Google之後,我鎖定了C Interfaces and Implementation——另一本關於如何寫出狂炫酷帥叼炸天的C代碼的奇書,這裡套用下Amazon的評論:Probably the best advanced C book in existance。

嚴格來說上面兩本書都不是傳統的演算法書,因為它們側重的都不是演算法,而是經典演算法的具體實現(Implementation),然而這正是我所需要的:因為演算法的原理我能說明白,但要給出優雅正確簡練的實現我就傻逼了,哪怕是stof這種簡單到爆的」演算法」。

依然是以前的傻逼學習方法:反覆研讀+一遍又一遍的把代碼抄寫到本子上,艱難的完成了這兩本書後,又讀了相當數量的編程實踐(Programming Practice)書籍,自我感覺編程能力又大幅提升,此外獲得新技能——紙上編碼。這也成為了我之後找工作面試的三板斧之一。

應用

說老實話,自從本科實習之後,我就一直覺得演算法除了面試時能用用,其它基本用不上,甚至還寫了一篇當時頗為自得現在讀起來極為傻逼的文章來黑那些動不動就」基礎」或」內功」的所謂」大牛」們,這裡摘取一段現在看起來很傻逼但當時卻覺得是真理的文字:

所以那些動則就扯什麼演算法啊基礎啊內功啊所謂的大牛們,請閉上你的嘴,條條大道通羅馬。演算法並不是編程的前提條件,數學也不會阻礙一個人成為優秀的程序員。至少在我看來,什麼演算法基礎內功都是唬人的玩意,多編點能用的實用的程序才是王道,當然如果你是一個pure theorist的話就當我什麼都沒說好了。

然而有意思的是,寫了這篇文章沒多久,鼓吹演算法無用論的我自己做的幾個大大小小的項目全部用到了演算法——我疑心是上天在有意抽我的臉。

LL(k)

我在微軟實習的第一個項目做的是代碼覆蓋率分析——計算T-SQL存儲過程的代碼覆蓋率。

簡單的看了下SQL Server相關的文檔,我很快發現SQL Reporting Service可以記錄T-SQL的執行語句及行號,於是行覆蓋(line coverage)搞定,但老大說行覆蓋太naive,我們需要更實際的塊覆蓋(block coverage)。

閱讀了塊覆蓋的定義後,我發現我需要對T-SQL進行語法分析,在沒有找到一個好用的T-SQL Parser的情況下,只能自己動手搞一個:

比較奇詭的是,做這個項目時當時我剛好把ANTLR作者的Language Implementation Patterns看了一半,什麼LL(k)啊Packrat啊AST Walker的概念啊正熱乎著呢。

於是,自己自己就照著T-SQL的官方EBNF,三下五除二擼了一個T-SQL存儲過程的LL(k) Parser,把代碼轉換成AST,然後用一個External AST Walker生成代碼塊覆蓋的HTML報表,全部過程一周不到。

老大自然是很滿意——我疑心他的原計劃是花兩三個月來完成這個項目,因為這個項目之後的兩個月我都沒什麼活干,天天悠哉游哉。

拼音索引

拼音索引是我接的一個手機應用私活里的小模塊,用戶期待在手機文本框可以根據輸入給出智能提示:
比如說輸入中國:

同樣,輸入拼音也應給出提示:

中文匹配這個簡單,但拼音匹配就得花時間想想了——懶得造輪子的我第一時間找到了微軟的拼音庫,但接下來我就發現微軟這個鳥庫在手機上跑不動,研究了下發現WP7對Dictionary的items數量有限制,貌似是7000還是8000個item就會崩盤,而標準漢字則有兩萬多個,尼瑪。

痛罵MS坑爹+漢字坑爹之餘,還是得自己擼一個庫出來:

  1. 首先把那兩萬個漢字搞了出來,排序,然後弄成一個超長的字元串。
  2. 接下來用Int16索引了漢字所有的拼音(貌似500多個)。
  3. 再接下來用Int64建立漢字和拼音的關聯——漢字有多音字,所以需要把多個拼音pack到一個Int64里,這個簡單,位操作就搞定。
  4. 最後用二分+位移Unpack,直接做到從漢字到拼音的檢索。
  5. 後來小測了下性能,速度是MS原來那個庫的五十倍有餘,而代碼量只有336行。

用戶很happy——因為我捎帶把他沒想到的多音字都搞定了,而且流暢的一逼。

我也很happy,因為沒想到自己寫的庫居然比MS的還要快幾十倍,同時小十幾倍。

從這個事情之後我變得特別理解那些造輪子的人——你要想想,如果你需要一個飛機輪子但市場上只有自行車輪子而且老闆還催著你交工,你能怎麼搞。

快速字元串匹配

前面提到在微軟實習時老大扔給我一個Windows Phone讓我研究下,我當時玩了玩就覺著不太對勁,找聯繫人太麻煩。

比如說找」張曉明」,WP只支持定位到Z分類下——這意味著我需要在Z分類下的七十多個聯繫人(姓張的姓趙的姓鐘的等等)裡面線性尋找,每次我都需要滑動四五秒才能找到這個張姓少年。

這TMD也太傻逼了,本屌三年前的老破NOKIA都支持首字母定位,996-&>ZXM-&>張曉明,直接搞定,尼瑪一個新時代Windows Phone居然會弱到這個程度。

搜了一下發現沒有好用的撥號程序,於是本屌就直接擼了一個支持首字母匹配的撥號程序出來扔到WP論壇里。

結果馬上就有各種問題出現——最主要的反映是速度太慢,一些用戶甚至反饋按鍵有時要半秒才有反應。本屌問了下他的通訊錄大小:大概3000多人。

吐槽怎麼會有這麼奇葩的通訊錄之餘,我意識到自己的字元串匹配演算法存在嚴重的性能問題:讀取所有人的姓名計算出拼音,然後一個個的匹配——結果如果聯繫人數量太多的話,速度必然拙計。

於是我就開始苦思冥想有沒有一個能夠同時搜索多個字元串的高端演算法,以至於那兩天坐地鐵都在嘟囔怎麼才能把這個應用搞的快一些。

最終還是在Algorithms on Strings, Trees and Sequences里找到了答案——確實有能夠同時搜索多個字元串的方法:Tries,而且這本書還用足足一章來講怎麼弄Multiple string comparison,看得我當時高潮迭起,直呼過癮。

具體細節不多說,總之換了演算法之後,匹配速度快了大約九十多倍,而且代碼還短了幾十行。哪怕是有10000個聯繫人,也能在0.1秒內搞定,速度瓶頸就這樣愉快的被演算法搞定。

Writing Efficient Programs

之後又做了若干個項目,多多少少都用到了」自製」的演算法或數據結構,最奇詭的一次是寫一個電子書閱讀器里的分頁,我照著模擬退火(Simulated Annealing)的原理寫了一個快速分頁演算法,事實上這個演算法確實很快——但問題是我都不知道為啥它會這麼快。

總之,演算法是一種將有限計算資源發揮到極致的武器,當計算資源很富餘時演算法確實沒大用,但一旦到了效率瓶頸演算法絕壁是開山第一刀(因為演算法不要錢嘛!要不還得換CPU買SSD升級RAM,肉疼啊!!)。一些人會認為這種說法是有問題,因為編寫新演算法的人力成本有時比增加硬體的成本還要高——但別忘了增加硬體提升效率也是建立在演算法是Scalable的基礎上——說白了還是得擼演算法。

說到優化這裡順帶提一下Writing Efficient Programs——很難找到一本講代碼優化的書(我疑心是自從Knuth說了過早優化是萬惡之源之後沒人敢寫,萬惡之源嘛,寫它干毛),注意這本書講的是代碼優化——在不改變架構、演算法以及硬體的前提之下進行的優化。儘管書中的一些諸如變數復用或是循環展開的trick已經過時,但總體仍不失為一本好書。

提高

實習實習著就到了研二暑假,接下來就是求職季。

求職季時我有一種莫名的復仇感——尼瑪之前百度實習面試老子被你們黑的漫天飛翔,這回求職老子要把你們一個個黑回來,尼瑪。

現在回想當時的心理實屬傻逼+幼稚,但這種黑暗心理也起了一定的積極作用:我絲毫不敢有任何怠慢,以至於在5月份底我就開始準備求職筆試面試,比身邊的同學早了兩個月不止。

我沒有像身邊的同學那般刷題——而是繼續看書抄代碼學演算法,因為我認為那些難得離譜的題面試官也不會問——事實上也是如此。

Algorithm Design Manual

因為很多Coding Interview的論壇都提到這本紅皮書,我也跟風搞了一本。事實證明,僅僅是關於Backtrack Template那部分的描述就足以值回書價,更不用說它的Heuristics和課後題。

編程珠璣更多的編程珠璣

這兩本書就不用多介紹,編程珠璣和更多的編程珠璣,沒聽說過這兩本書請自行面壁。前者偏演算法理論,後者偏演算法軼事,前者提升能力,後者增長談資,都值得一讀。

The Science of Programming

讀到編程珠璣裡面關於Binary Search的正確性證明時我大呼過癮,原來程序的正確性也是可以推導的,然後我就在那一章的引用里發現David Gries的The Science of Programming。看名字就覺得很厲害,直接搞了一本開擼。

不愧為編程珠璣引用的書籍,擼完The Science of Programming之後,本屌獲得了證明簡單代碼段的正確性這個技能——求職面試三板斧之二。

證明簡單代碼段的正確性是一個很神奇的技能——因為面試時大多數公司都會要求在紙上寫一段代碼,然後面試官檢查這段代碼,如果你能夠自己證明自己寫的代碼是正確的,面試官還能挑剔什麼呢?

之後就是各種面試,詳情見之前的博客,總之就是項目經歷紙上代碼正確性證明這三板斧,摧枯拉朽。

進化

求職畢業季之後就是各種Happy,Happy過後本屌發現即將面臨另一個問題:演算法能力不足。

因為據說以後的同事大多是ACM選手,而本屌從來沒搞過演算法競賽,而且知道的演算法和數據結構都極為基礎:像那些元胞自動機、斐波那契堆或是線段樹這些高端數據結構壓根只是能把它們的英文名稱拼寫出來,連用都沒用過,所以心理忐忑的一逼。

為了不至於到時入職被鄙視的太慘烈,加上自己一貫的演算法自卑症,本屌強制自己再次學習演算法:

Algorithms 4th

Algorithms是我重溫演算法的第一本書,儘管它實際就是一本數據結構的入門書,但它確實適合當時已經快把演算法忘光的本屌——不為學習,只為重溫。

這本書最大的亮點在於它把Visualization和Formatting做到了極致——也許它不是最好的數據結構入門書,但它絕壁是我讀過的排版最好的書,閱讀體驗爽的一逼;當然這本書的內容也不錯,尤其是紅黑樹那一部分,我想不會有什麼書會比此書講的更明白。

6.851 Advanced Data Structures

Advanced Data Structures是MIT的高級數據結構教程,為什麼會找到這個教程呢?因為Google Advanced Data Structures第一個出來的就是這貨。

這門課包含各種讓本屌世界觀崩壞的奇詭數據結構和演算法,它們包括但不限於:

  • 帶」記憶」的數據結構(Data Structure with Persistence)。
  • van Emde Boas(逆天的插入,刪除,前驅和後繼時間複雜度)。
  • o(1)時間複雜度的的LCA、RMQ和LA解法。
  • 奇幻的o(n)時間複雜度的Suffix Tree構建方法。
  • o(lglgn)的BST。


總之高潮迭起,分分高能,唯一的不足就是沒有把它們實現一圈。以後本屌一定找時間把它們一個個擼一遍。

總結

從接觸演算法到現在,大概七年:初學時推崇演算法牛逼論,實習後鼓吹演算法無用論,讀研後再被現實打回演算法牛逼論。

怎麼這麼像辯證法里的肯定到否定再到否定之否定。

現在來看,相當數量的鼓吹演算法牛逼論的人其實不懂演算法的重要性——如果你連用演算法解決實際問題的經歷都沒有,那你如何可以證明演算法很有用?而絕大多數鼓吹演算法無用論的人不過是低水平碼農的無病呻吟——他們從未碰到過需要用演算法解決的難題,自然不知道演算法有多重要。

Peter Norvig曾經寫過一篇非常精彩的SICP書評,我認為這裡把SICP換成演算法依然適用:

To use an analogy, if algorithms were about automobiles, it would be for the person who wants to know how cars work, how they are built, and how one might design fuel-efficient, safe, reliable vehicles for the 21st century. The people who hate algorithms are the ones who just want to know how to drive their car on the highway, just like everyone else.

MIT教授Erik Demaine則更為直接:

If you want to become a good programmer, you can spend 10 years programming, or spend 2 years programming and learning algorithms.

總而言之,如果你想成為一個碼農或是熟練工(Code Monkey),你大可以不學演算法,因為演算法對你確實沒有用;但如果你想成為一個優秀的開發者(Developer),紮實的演算法必不可少,因為你會不斷的掉進一些只能藉助演算法才能爬出去的坑裡。

以上。


學習路線應該是這樣,從淺入深:
前提:了解一門語言。
第一步:先了解基本的數據結構,棧、隊列、樹、圖、簡單排序等;一般高校教材基本滿足。

第二步:如果還在上學,抓緊機會學習好概率論、數理統計、微積分、線性代數,最優化,為以後進階打好基礎;(概率和微積分尤為重要)。如果只想了解常見演算法,這步可略。如果想在演算法上走的更遠,數學基本功一定需要下功夫;

第三步:來吧,不用說,上《演算法導論》,第一階段看懂演算法,盡量實現一遍;第二階段看懂證明;第三階段習題基本思考一遍;

實習、項目、編程、練習一定要伴隨左右,無練習無提高;

第四步:繼續進階,深入了解一個領域,或圖像信號模式識別、或統計學習人工智慧、或編譯原理底層優化等等;例如你選擇人工智慧之路,那麼看《統計學習》、《數據挖掘》、《神經網路》;

第五步:找個好項目鍛煉自己的能力,在實踐中加深理解。

第六步:看論文,改進已有演算法,或提出更佳演算法;

再往上就不知道了...

總之,保持激情、保持好奇心,一路向前,終將有所收穫。


選一本經典的演算法書籍,認真思考演算法思路,然後要做練習題,隨後可以去做做TopCoder。我演算法不強,不過我是這樣學的,僅供參考,謝邀了。


我回答過的幾個問題,題主可以參考下:
作為一個低級碼農,該怎樣跳到一個演算法崗位? - SimonS 的回答
程序員必須掌握哪些演算法? - SimonS 的回答
互聯網公司最常見的面試演算法題有哪些? - SimonS 的回答


How Do I Learn Data Structures and Algorithms?


演算法不用研究太深,把演算法導論全刷完就行了,刷題什麼也沒必要,有幾個出名的題庫幾百道題而已,刷完就行了。陷得太深就沒精力搞別的了。
學習的話,第一本可以選擇演算法第四版,或者是數據結構與演算法分析。都是入門書,寫得非常好。數據結構還可以參考演算法精解和STL的實現,提升代碼品味。
然後就開始學演算法導論吧。前半本見到,講數據結構的。後半本是各種常見題,多看看。數據結構能閉著眼睛寫紅黑樹,寫圖我覺得就差不多了。


首先題主沒說自己是在讀還是在職;

題主也沒說到底是計算機演算法還是機器學習類的演算法。。

所以我就假設題主其實不大清楚其中區別咯。。

上面都是說計算機類的演算法,我想說說數學方面的演算法。。

雖然我也不能說給別人指導什麼的,不過感覺心路歷程可以拿出來分享一下:

剛開始上大學呢,聽別人說演算法很重要,那時候也很有激情,對各種東西都想了解下,比如opengl啊、分形啊什麼的,裡面也確實有些涉及到演算法的東西,比如法線的計算、仿射變換等等,後來上數據結構接觸了avl樹這些東西,也曾經想過往這方面發展;

嗯,然後我對編譯原理其實也很感興趣,當時就聽說隔壁班的vczh在大一就擼編譯器了;

後來在畢業設計的時候,老闆丟給我一篇論文翻譯,關於神經網路在經濟模型中的預測(當時其實沒看懂,單純覺得高大上),然後到了讀研的期間,才總算是認清楚自己的興趣其實一直都沒變過,是在數學方面的演算法,我想表達的是,如果有條件,最好還是先認清楚自己,搞清楚到底是哪方面的演算法;

如果是數據挖掘之類的演算法:

首先數學的兩個基本分支上不能太差:分析學、代數學;比如給你個公式求梯度,求hessian矩陣什麼的。。然後就是告訴你一個函數是凸的,你也得大概有個概念,為什麼凸函數用梯度下降法能收斂,至於證明什麼的,如果真的要深入也是要懂的,這部分基本上就是分析、代數的內容,以及兩者的結合——凸優化,其實大學的理工課程修完了,多多少少也懂些基礎,總之就是給你一個優化問題,你大概知道是怎麼回事,主要是有個簡單的理解;

然後可以繼續深入一些無約束優化的演算法:精確、不精確綫搜索啊,梯度下降、最速下降啊,牛頓法,共軛方向及共軛梯度,擬牛頓法這些,這時候可以考慮一下用程序寫一寫,不考慮效率,這個過程順便可以鍛煉一下設計模式,因為涉及到矩陣運算的東西,就會有實矩陣、復矩陣(其實不是必須的),如果你要像mathematica那樣的符號運算,甚至實矩陣裡面還能繼承一個「分數矩陣」出來;總之在這個過程是能鍛煉一下實際的編碼能力的;

如果搞明白無約束優化,這時候應該已經可以理解一些機器學習演算法了,比如logistic回歸啦(不帶正則化),比如基於lms的adaline網路和多層感知機的bp演算法啦等等;到了這一步,可能就會考慮更深層的問題了,比如一些最優化演算法為什麼能收斂,收斂速度等,這時候可能會回頭看看分析和代數的內容;

如果要搞svm,這就是個深坑了,首先要搞明白帶約束條件的優化問題是怎麼回事,然後要理解對偶問題的轉化(以及為什麼可轉化、什麼條件可轉化),然後會遇到kernel(以及什麼樣的kernel是合要求的),還有軟間隔,最後得到一個最終的優化問題,然後你發現這個問題求解會很慢,接著自然就是smo了,然後為什麼smo可行。。。。

如果不這麼深入也是可以的,能轉化為對偶問題、對綫性核多項式核rbf核的原理知道一點、能理解「泛化能力」,我覺得已經可以實用化了,但是通用的東西比如內點法、外點法、乘子法這些我覺得還是了解下比較好;

最後有不少模型是需要概率論裡面比較深入的內容去支持的,比如EM過程,單純的實現不難,但是你要知道為什麼收斂、適用於什麼場景下,就需要深入了解模式識別一些體系性的內容了;再比如另外一些演算法是需要有隨機過程基礎的,這部分我還在努力中就不亂說了。。

================================================================

總結一下需要的內容,無非是理工科本科一些基礎數學課程(數學分析、綫性代數、概率論和多元統計分析),還有凸優化(這個有些學校本科,有些碩士),加上一兩門實戰的語言(如果只是要用工具那這個可以忽略),如果是寫演算法的恐怕還要搞搞數值演算法(qr分解、householder變換那些),最後就是落實到一些實在的分類、聚類等模型上;

有些時候過程可能是反的,先懂應用,再懂原理;

大的過程沒能力給了,以上都是比較細的東西,希望有幫助


大家可以看一下這個網站:Dev-XYS/Algorithms


先學數據結構,然後看演算法入門書,推薦《趣學演算法》,有大量圖解,比較簡單,容易懂,而且有源碼下載直接運行。

傳統的演算法書,大多注重內容的收錄,但卻忽視思維過程的展示,因此我們學習了經典的演算法,卻費解於演算法設計的過程。遇到一個實際問題,通過問題分析,選擇使用什麼樣的演算法策略,基於這種演算法策略選擇什麼樣的數據結構,有時演算法策略和數據結構的選擇並不是唯一的,不同的演算法策略和數據結構設計的演算法,其複雜性是不同的。而很多書就是灌輸式的講一個實例,一下子就選擇了一個認定是最優的演算法策略,告訴你就這樣干,不談數據結構,然後分析演算法複雜性,就結束了。原則上講演算法策略就講演算法策略,不依賴任何程序設計語言和數據結構,但對很多學生來講,尤其是語言沒學好,數據結構也不熟練的同學,只講演算法策略,如同空中樓閣。自己用演算法解決實際問題,一頭霧水。

剛入門者不建議直接看《演算法導論》,雖然它是經典,不適合初學者,會看蒙圈。

演算法入門推薦《趣學演算法》,這本書有大量圖解,適合初學者,從問題出發,根據實際問題進行分析,選擇合適的演算法策略,並分析為什麼採用這種演算法策略,然後選擇什麼數據結構,不同的數據結構複雜性會有什麼區別,巧妙地將數據結構和演算法策略擰成了一條線。通過大量實例,充分展現演算法設計的思維過程,讓學生充分體會遇到一個問題,如何分析,使用什麼演算法策略,採用什麼數據結構,演算法的複雜性如何?是否有優化的可能?


推薦閱讀:

你壓力最大的時候是什麼時候,怎麼度過的?
想從事數據分析工作,學什麼軟體或語言最好?
想做 Python 聊天機器人,有什麼好用的中文分詞、數據挖掘、AI方面的 Python 庫或者開源項目推薦?
診脈驗孕,有沒有可能用數字化的方法驗證可靠性?一定要來個挑戰賽么?
如何用Python3寫一段將Excel數據導入SQL資料庫?

TAG:演算法 | 數據挖掘 | 計算機 | 學習方法 |