你需要知道的算法之基礎篇

Nino 發布于2019-08-22 11:19 / 1270人閱讀

摘要：你需要知道的算法之基礎篇前言很多時候我們都會感慨要是當時了多好啊，現在也不至于這樣難堪了。但是我們不可能又沒必要對每個算法進行測試，只需要知道大概的哪個算法執行所花費的時間多，哪個花費的時間少就行了。

你需要知道的算法之基礎篇 0 - 前言

很多時候我們都會感慨：要是當時×××了多好啊，現在也不至于這樣難堪了。

后悔的時候千千萬，一覺醒來過眼云煙。

我也和蕓蕓眾生一樣在學校的時候沒有好好的理解思考一些東西，等到了真正需要用的時候才知道書到用時方恨少。有道是知錯能改，那為什么有道 == 知錯能改呢？下面請允許我開始真正的內容：

本文通篇都是一些概念，但是你需要知道這些更有利于理解時間復雜度等一些概念是什么、怎么來的、為什么需要這個東西(what、where、why)。

1 - 算法

算法的定義是這樣的：解題方案的準確而完善的描述，是一系列解決問題的清晰指令。巴拉巴拉的，雖然是一小句但還是不想看（題外話：有時候吧專業名詞記下來面試的時候還是挺有用的），其實就是解決一個問題的完整性描述。只不過這個描述就可能是用不同的方式或者說是“語言”了。

2 - 算法的效率

既然算法是解決問題的描述，那么就像一千個人眼中有一千個阿姆雷特他大姨夫一樣，解決同一個問題的辦法也是多種多樣的，只是在這過程中我們所使用/消耗的時間或者時間以外的代價（計算機消耗的則為內存了）不一樣。為了更快、更好、更強的發揚奧利奧..哦不，提高算法的效率。所以很多時候一個優秀的算法就在于它與其他實現同一個問題的算法相比，在時間或空間（內存）或者時間和空間（內存）上都得到明顯的降低。

所以呢，算法的效率主要由以下兩個復雜度來評估：

時間復雜度：評估執行程序所需的時間。可以估算出程序對處理器的使用程度。

空間復雜度：評估執行程序所需的存儲空間。可以估算出程序對計算機內存的使用程度。

設計算法時，時間復雜度要比空間復雜度更容易出問題，所以一般情況一下我們只對時間復雜度進行研究。一般面試或者工作的時候沒有特別說明的話，復雜度就是指時間復雜度。

2.0 - 時間復雜度

接下來我們還需要知道另一個概念：時間頻度。這個時候你可能會說：“不是說好一起學算法嗎，這些東東是什么？贈品嗎？”。非也非也，這是非賣品。

因為一個算法執行所消耗的時間理論上是不能算出來的，沒錯正是理論上，so我們任然可以在程序中測試獲得。但是我們不可能又沒必要對每個算法進行測試，只需要知道大概的哪個算法執行所花費的時間多，哪個花費的時間少就行了。如果一個算法所花費的時間與算法中代碼語句執行次數成正比，那么那個算法執行語句越多，它的花費時間也就越多。我們把一個算法中的語句執行次數稱為時間頻度。通常（ps:很想知道通常是誰）用T(n)表示。

在時間頻度T(n)中，n又代表著問題的規模，當n不斷變化時，T(n)也會不斷地隨之變化。為了了解這個變化的規律，時間復雜度這一概念就被引入了。一般情況下算法基礎本操作的重復執行次數為問題規模n的某個函數，用也就是時間頻度T(n)。如果有某個輔助函數f(n)，當趨于無窮大的時候，T(n)/f(n)的極限值是不為零的某個常數，那么f(n)是T(n)的同數量級函數，記作T(n)=O(f(n))，被稱為算法的漸進時間復雜度，又簡稱為時間復雜度。

2.1 - 大O表示法

用O(n)來體現算法時間復雜度的記法被稱作大O表示法

一般我們我們評估一個算法都是直接評估它的最壞的復雜度。

大O表示法O(f(n))中的f(n)的值可以為1、n、logn、n^2 等，所以我們將O(1)、O(n)、O(logn)、O( n^2 )分別稱為常數階、線性階、對數階和平方階。下面我們來看看推導大O階的方法：

推導大O階

推導大O階有一下三種規則：

用常數1取代運行時間中的所有加法常數

只保留最高階項

去除最高階的常數

舉好多栗子

常數階

let sum = 0, n = 10; // 語句執行一次
let sum = (1+n)*n/2; // 語句執行一次
console.log(`The sum is : ${sum}`) //語句執行一次

這樣的一段代碼它的執行次數為 3 ，然后我們套用規則1，則這個算法的時間復雜度為O(1)，也就是常數階。

線性階

let i =0; // 語句執行一次
while (i < n) { // 語句執行n次
  console.log(`Current i is ${i}`); //語句執行n次
  i++; // 語句執行n次
}

這個算法中代碼總共執行了 3n + 1次，根據規則 2->3，因此該算法的時間復雜度是O(n)。

對數階

let number = 1; // 語句執行一次
while (number < n) { // 語句執行logn次
  number *= 2; // 語句執行logn次
}

上面的算法中，number每次都放大兩倍，我們假設這個循環體執行了m次，那么2^m = n即m = logn，所以整段代碼執行次數為1 + 2*logn，則f(n) = logn，時間復雜度為O(logn)。

平方階

for (let i = 0; i < n; i++) { // 語句執行n次
  for (let j = 0; j < n; j++) { // 語句執行n^2次
    console.log("I am here!"); // 語句執行n^2
  }
}

上面的嵌套循環中，代碼共執行 2*n^2 + n，則f(n) = n^2。所以該算法的時間復雜度為O(n^2 )

常見時間復雜度的比較

常見的時間復雜度函數相信大家在大學中都已經見過了，這里也不多做解釋了：

O(1) 3 - 結語

曾經有一份能夠在學校好好學算法的機會，我沒有好好珍惜，直到失去的時候我才追悔莫及。

從今天開始，我會好好的把之前很多自己沒有去理解的各種基礎、底層知識好好的嚼幾遍。與諸君共勉！

原文地址：點擊此處

GPU云服務器云服務器之基礎篇你知道你應該知道學習算法需要什么基礎

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/92192.html

我的阿里之路+Java面經考點

摘要：我的是忙碌的一年，從年初備戰實習春招，年三十都在死磕源碼，三月份經歷了阿里五次面試，四月順利收到實習。因為我心理很清楚，我的目標是阿里。所以在收到阿里之后的那晚，我重新規劃了接下來的學習計劃，將我的短期目標更新成拿下阿里轉正。我的2017是忙碌的一年，從年初備戰實習春招，年三十都在死磕JDK源碼，三月份經歷了阿里五次面試，四月順利收到實習offer。然后五月懷著忐忑的心情開始了螞蟻金...

姘擱『 2019-08-15 14:42 評論0 收藏0
自學人工智能之數學篇，數學入門并不難

摘要：寫本文的目的，希望結合眾家之長，試圖解決數學對機器學習入門的困擾。這里假設你上過大學的數學課，你就具備了機器學習的數學入門門檻了，之后的數學啃一啃是可以下來的。寫這篇文章很久想了很久，到底該怎么寫？關于數學與機器學習的關系，觀點很多。寫本文的目的，希望結合眾家之長，試圖解決數學對機器學習入門的困擾。現在數學困擾大家主要有這幾個方面： 1、機器學習需要的數學知識是不是很難，網上...

fox_soyoung 2019-06-26 18:32 評論0 收藏0
自學人工智能之數學篇，數學入門并不難

摘要：寫本文的目的，希望結合眾家之長，試圖解決數學對機器學習入門的困擾。這里假設你上過大學的數學課，你就具備了機器學習的數學入門門檻了，之后的數學啃一啃是可以下來的。寫這篇文章很久想了很久，到底該怎么寫？關于數學與機器學習的關系，觀點很多。寫本文的目的，希望結合眾家之長，試圖解決數學對機器學習入門的困擾。現在數學困擾大家主要有這幾個方面： 1、機器學習需要的數學知識是不是很難，網上...

txgcwm 2019-07-30 17:17 評論0 收藏0