創作時間:2019-03-17
作者:周林
版權所有,轉載請聯繫作者獲取授權、並註明作者與出處
今日頭條同步鏈接
周林的簡書主頁
周林的CSDN博客主頁
周林的知乎主頁
寫在前面的話
在互聯網、大數據、人工智慧火爆的今天,「演算法」這個詞幾乎婦孺皆知,業已成為「高薪」「牛X」的代名詞。應不少朋友的邀請,特連載本系列,旨在用最通俗的方式——「講人話、無廢話、看得懂、用得上」——將位於神龕之上的演算法送進尋常百姓家。
本篇作為系列的第一篇,採用「What、Why、How」文章結構,來給大家普及一下演算法的基本概念(也糾正一些朋友的錯誤概念)。
What is Algorithm?(演算法是個什麼鬼 )
為不落入俗套,本文不會重複wiki上「演算法」的官方定義,而採用啟發式結構來闡述演算法的本質:
試想平時在遇到問題的時候,我們是如何解決的。樸素而廣泛的過程方法論如下:
1. 重新定義問題,結構化描述
2. 根據重定義,歸類問題
3. 根據問題類別,做經驗匹配
4. 根據匹配結果,分支處理:若匹配,採用經驗方法;若匹配不上,設計開發新方法
5. 迭代更新經驗庫,增強面向未來問題的能力
與演算法相關的就是上面的第3步~第5步。
簡單來說,演算法本質是:解決某類問題的方法。如果方法已經在經驗庫裏了,直接拿來主義,也就是「既有演算法」;如果不在,那麼設計開發的新方法,新方法就是「新演算法」。當然還有一種情況:雖然經驗庫裏有針對該類問題的方法了,但是設計開發了一個更有效的新方法,那麼也稱為「新演算法」。
下面來對幾個關鍵點進行闡述:
什麼是「更有效的演算法」?
「更有效」的背後邏輯其實比較的就是「代價」,或者稱為「開銷」。經濟上衡量就是成本,它分為兩個維度:時間成本和資源成本。資源成本在計算機上的體現就是硬碟、內存、CPU等一系列硬體資源開銷。對這些硬體資源開銷進一步抽象,就是空間成本。從學科分類上講,演算法其實屬於計算數學,計算數學屬於應用數學。用專業術語來描述時間成本與空間成本,就是計算複雜度,很自然地,它也有兩個維度:時間複雜度和空間複雜度。描述複雜度的數學符號是O()。後面我們會詳細介紹O()的表達。
綜上所述,所謂的「更有效」的演算法,指的就是時間複雜度或者空間複雜度更優的演算法。
為什麼要「重新定義問題,結構化描述」?
把人腦也看做一臺機器的話,很顯然這臺機器的運行方式和效率與計算機有所不同(儘管現在的機器學習在儘可能地模擬人腦的機理,但是兩者至少在現階段還有本質不同)。人腦在連續信號和非結構化場景下的處理能力是卓越的,但是計算機只能處理離散信號,並且必須最終轉化成結構化數據才能進行處理(儘管現在的機器學習可以通過自我學習來將數據結構化)。用一張圖來描述這個過程就是: