邂逅數據結構&演算法

可能你之前經常聽說數據結構和演算法, 但是不知道他們在討論什麼.

因為似乎我們學習編程的過程中, 沒有必要了解這些, 我只是在學習基本的語法/高級語法/做出界面效果/實現複雜的邏輯.

數據結構和演算法? 它是什麼? 為什麼它如此重要?

一. 什麼是數據結構和演算法?

數據結構和演算法的概念還真不是那麼好定義.

什麼是數據結構?

官方定義: 並沒有…

民間定義:

「數據結構是數據對象，以及存在於該對象的實例和 組成實例的數據元素之間的各種聯繫。這些聯繫可以

通過定義相關的函數來給出。」 —- 《數據結構、演算法與應用》

「數據結構是ADT（抽象數據類型 Abstract Data Type）的物理實現。」 —- 《數據結構與演算法分析》

「數據結構（data structure）是計算機中存儲、組織數據的方式。通常情況下，精心選擇的數據結構可以 帶來最優效率的演算法。」 —-中文維基百科

從上面的定義, 我們可以發現數據結構和演算法的關係非常的緊密

我們還是從自己的角度來認識數據結構吧:

在計算機中, 存儲和組織數據的方式

我們知道, 計算機中數據量非常龐大, 如何以高效的方式組織和存儲呢?

這就好比一個龐大的圖書館中存放了大量的書籍, 我們不僅僅要把書放進入, 還應該在合適的時候能夠取出來

我們從擺放圖書說起

如果是自己的書相對較少, 我們可以這樣擺放

如果你有一家書店, 書的數量相對較多, 我們可以這樣擺放

如果我們開了一個圖書館, 書的數量相當龐大, 我們可以這樣擺放

圖書擺放要使得兩個相關操作方便實現:

操作1：新書怎麼插入？

操作2: 怎麼找到某本指定的書？

圖書各種擺放方式:

方法1：隨便放

操作1：哪裡有空放哪裡，一步到位！

操作2: 找某本書, 累死…

方法2：按照書名的拼音字母順序排放

操作1: 新進一本《阿Q正傳》, 按照字母順序找到位置, 插入

操作2: 二分查找法

方法3: 把書架劃分成幾塊區域, 按照類別存放, 類別中按照字母順序

操作1: 先定類別，二分查找確定位置，移出空位

操作2: 先定類別，再二分查找

結論:

解決問題方法的效率, 根數據的組織方式有關

計算機中存儲的數據量相對於圖書館的書籍來說數據量更大, 數據更加多

以什麼樣的方式, 來存儲和組織我們的數據才能在使用數據時更加方便呢?

這就是數據結構需要考慮的問題

常見的數據結構

比較常見的數據結構

常見的數據結構較多, 每一種都有其對應的應用場景, 不同的數據結構的不同操作性能是不同的:

有的查詢性能很快,有的插入速度很快,有的是插入頭和尾速度很快

有的做範圍查找很快,有的允許元素重複,有的不允許重複等等

在開發中如何選擇,要根據具體的需求來選擇

注意: 數據結構和語言無關, 基本常見的編程語言都有直接或者間接的使用上述常見的數據結構

為什麼之前學習JavaScript沒有接觸過數據結構呢? 好像只見過數組.

單純從客戶程序員的角度, 我們並不需要過多的了解它們的實現細節.

但是簡單的使用不能讓我們更加靈活的使用它們. 了解真相, 你才能獲得真正的自由.

什麼是演算法?

演算法(Algorithm)的認識

在之前的學習中, 我們可能學習過幾種排序演算法. 並且知道, 不同的演算法, 執行效率是不一樣的.

也就是說進行某些操作的過程中, 不僅僅數據的存儲方式會影響效率, 演算法的優劣也會影響著效率

那麼到底什麼是演算法呢?

演算法的定義:

一個有限指令集, 每條指令的描述不依賴於語言

接受一些輸入（有些情況下不需要輸入）

產生輸出

一定在有限步驟之後終止

演算法通俗理解:

Algorithm這個單詞本意就是解決問題的辦法/步驟邏輯.

數據結構的實現, 離不開演算法.

舉例：電燈不工作的解決演算法

二. 生活中的數據結構和演算法

前面我們提了一下生活中的數據結構和演算法: 圖書的擺放.

為了更加方便的插入和搜索書籍, 需要合理的組織數據, 並且通過更加高效的演算法插入和查詢數據.

除了這些, 生活中還有很多案例.

數據結構的案例

快遞員的快遞

上大學期間不知道大家有沒有收過快遞.

大學的快遞通常情況不是送到宿舍的(要不快遞員不願意挨著去送, 要不宿舍壓根不讓進), 通常快遞會放在某個固定的地方, 讓大家自己去拿.

當你跑到固定的地方拿快遞, 還有兩種情況: 一種自己去海量的快遞中找, 另一種快遞員讓你報出名字, 它幫你找.

自己尋找相當於線性查找, 一個個挨著看吧. 當然我們人類眼睛處理數據的能力非常快, 眼觀六路耳聽八方, 可能很快也能找到.

但是比較好的方式, 應該是快遞員幫我們找. 如果這個快遞員動動腦筋的話, 最好的方式是對快遞進行分類, 比如按照名字分類.

這個時候, 只要你報出名字, 它會根據姓氏立馬鎖定到一塊快遞中, 再根據名字馬上幫你找到.

這就體現了合理的組織數據, 對於我們獲取數據效率的重要性至關重要.

演算法的案例

找出線纜出問題的地方:

假如上海和杭州之間有一條高架線, 高架線長度是1,000,000米, 有一天高架線中有其中一米出現了故障.

請你想出一種演算法, 可以快速定位到處問題的地方.

線性查找:

從上海的起點開始一米一米的排查, 最終一定能找到出問題的線段.

但是如果線段在另一頭, 我們需要排查1,000,000次. 這是最壞的情況. 平均需要500,000次.

二分查找:

從中間位置開始排查, 看一下問題出在上海到中間位置, 還是中間到杭州的位置.

查找對應的問題後, 再從中間位置分開, 重新鎖定一般的路程.

最壞的情況, 需要多少次可以排查完呢? 最壞的情況是20次就可以找到出問題的地方.

怎麼計算出來的呢?log(1000000, 2), 以2位底, 1000000的對數 ≈ 20.

結論:

你會發現, 解決問題的辦法有很多. 但是好的演算法對比於差的演算法, 效率天壤之別.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！