[[361250]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai 。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

數(shù)據(jù)結(jié)構(gòu)與算法是程序員內(nèi)功體現(xiàn)的重要標準之一，且數(shù)據(jù)結(jié)構(gòu)也應(yīng)用在各個方面，業(yè)界更有程序=數(shù)據(jù)結(jié)構(gòu)+算法這個等式存在。各個中間件開發(fā)者，架構(gòu)師他們都在努力的優(yōu)化中間件、項目結(jié)構(gòu)以及算法提高運行效率和降低內(nèi)存占用，在這里數(shù)據(jù)結(jié)構(gòu)起到相當重要的作用。此外數(shù)據(jù)結(jié)構(gòu)也蘊含一些面向?qū)ο蟮乃枷耄蕦W好掌握數(shù)據(jù)結(jié)構(gòu)對邏輯思維處理抽象能力有很大提升。

為什么學習數(shù)據(jù)結(jié)構(gòu)與算法?如果你還是學生，那么這門課程是必修的，考研基本也是必考科目。工作在內(nèi)卷嚴重的大廠中找工作數(shù)據(jù)結(jié)構(gòu)與算法也是面試、筆試必備的非常重要的考察點。如果工作了數(shù)據(jù)結(jié)構(gòu)和算法也是內(nèi)功提升一個非常重要的體現(xiàn)，對于程序員來說，想要得到滿意的結(jié)果，數(shù)據(jù)結(jié)構(gòu)與算法是必備功力!

數(shù)據(jù)結(jié)構(gòu)

概念

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。

簡言之，數(shù)據(jù)結(jié)構(gòu)是一系列的存儲結(jié)構(gòu)按照一定執(zhí)行規(guī)則、配合一定執(zhí)行算法所形成的高效的存儲結(jié)構(gòu)。在我們所熟知的關(guān)系數(shù)據(jù)庫、非關(guān)系數(shù)據(jù)庫、搜索引擎存儲、消息隊列等都是比較牛的大型數(shù)據(jù)結(jié)構(gòu)良好的運用。當然這些應(yīng)用中間件不單單要考慮單純的結(jié)構(gòu)問題。還考慮實際os、網(wǎng)絡(luò)等其他因素。

而對于數(shù)據(jù)結(jié)構(gòu)與算法這個專欄。我們程序員更改掌握的首先是在內(nèi)存中運行的抽象的數(shù)據(jù)結(jié)構(gòu)。是一個相對比較單一的數(shù)據(jù)結(jié)構(gòu)類型，比如線性結(jié)構(gòu)、樹、圖等等.

相關(guān)術(shù)語

在數(shù)據(jù)結(jié)構(gòu)與算法中，數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項很多人搞不清其中的關(guān)系。通過畫一張圖來捋一捋，然后下面舉個例子給大家分享一下。

用戶信息表users

Listlist;//數(shù)據(jù)對象list

class users 
{  
     //略 
     int id; 
     String name; 
     String sex; 
} 
//list和woman是數(shù)據(jù) 
List<users>list;//數(shù)據(jù)對象list 
List<users>woman;//數(shù)據(jù)對象woman 
list.add(new users(001,"bigsai","man"));//添加數(shù)據(jù)元素 一個users由（001，bigsai，man）三個數(shù)據(jù)項組成  
list.add(new users(002,"smallsai","man"));//數(shù)據(jù)元素 
list.add(new users(003,"菜虛鯤","woman"));//數(shù)據(jù)元素 
woman.add(list.get(2));//003,"菜虛鯤","woman"三個數(shù)據(jù)項構(gòu)成的一個數(shù)據(jù)元素 

數(shù)據(jù)：對客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的集合總稱。上述表中的三條用戶信息的記錄就是數(shù)據(jù)(也可能多表多集合這里只有一個)。這些數(shù)據(jù)一般都是用戶輸入或者是自定義構(gòu)造完成。當然，還有一些圖像、聲音也是數(shù)據(jù)。

數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素由若干數(shù)據(jù)項構(gòu)成!可認為是一個pojo對象、或者是數(shù)據(jù)庫的一條記錄。比如菜虛鯤那條記錄就是一個數(shù)據(jù)元素。

數(shù)據(jù)項：而構(gòu)成用戶字段/屬性的有id、name、sex等，這些就是數(shù)據(jù)項.數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的最小不可分割字段。可以看作一個pojo對象或者一張表(people)的一個屬性/字段的值。

數(shù)據(jù)對象：是相同性質(zhì)數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。比如上面的users表、list集合、woman集合都是數(shù)據(jù)對象。單獨一張表，一個集合都可以是一個數(shù)據(jù)對象。

總的捋一捋，數(shù)據(jù)范圍最廣，所有數(shù)據(jù)即數(shù)據(jù)，而數(shù)據(jù)對象僅僅是有相同性質(zhì)的一個集合，這個集合是數(shù)據(jù)的子集，但并不是數(shù)據(jù)的基本單位，而數(shù)據(jù)元素才是數(shù)據(jù)的基本單位。舉個例子表cat和表dog都是數(shù)據(jù)，然后表cat是個數(shù)據(jù)對象(因為都描述cat這種對象)，但是數(shù)據(jù)的基本單位并不是貓和狗，而是他們的具體的每一條，比如小貓咪1號，大貓咪二號，哈士奇1號，藏獒2號這些每一條才是數(shù)據(jù)的基本單位。

對于數(shù)據(jù)類型和抽象數(shù)據(jù)類型兩者容易混淆注意區(qū)分開：

數(shù)據(jù)類型

原子類型：其值不可再分的類型。比如int，char，double，float等。

結(jié)構(gòu)類型：其值可以再分為若干成分的數(shù)據(jù)類型。比如結(jié)構(gòu)體構(gòu)造的各種結(jié)構(gòu)等。

抽象數(shù)據(jù)類型(ADT)：抽象數(shù)據(jù)類型(ADT)是一個實現(xiàn)包括儲存數(shù)據(jù)元素的存儲結(jié)構(gòu)以及實現(xiàn)基本操作的算法。使得只研究和使用它的結(jié)構(gòu)而不用考慮它的實現(xiàn)細節(jié)成為可能。比如我們使用List、Map、Set等等只需要了解它的api和性質(zhì)功能即可。而具體的實現(xiàn)可能是不同的方案，比如List的實現(xiàn)有數(shù)組和鏈表不同選擇。

三要素

邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)就是順序表、鏈表之類。而非線性就是集合、樹、圖這些結(jié)構(gòu)。

存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(又稱映像，也稱物理結(jié)構(gòu))，存儲結(jié)構(gòu)主要分為順序存儲、鏈式存儲、索引存儲和散列(哈希)存儲，這幾種存儲通過下面這張圖簡單了解一下(僅僅為理解不考慮更多)：

數(shù)據(jù)的運算：施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn),運算的定義基于邏輯結(jié)構(gòu)，運算的實現(xiàn)基于存儲結(jié)構(gòu)。

在這里容易混淆的是邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的概念。對于邏輯結(jié)構(gòu)，不難看得出邏輯二字，邏輯關(guān)系也就是兩者存在數(shù)據(jù)上的關(guān)系而不考慮物理地址的關(guān)系，比如線性結(jié)構(gòu)和非線性結(jié)構(gòu)，它描述的是一組數(shù)據(jù)中聯(lián)系的方式和形式，他針對的是數(shù)據(jù)?？粗械氖菙?shù)據(jù)結(jié)構(gòu)的功能，比如線性表就是前后有序的，我需要一個有序的集合就可以使用線性表。

而存儲結(jié)構(gòu)就是跟物理地址掛鉤的。因為同樣邏輯結(jié)構(gòu)采用不同存儲結(jié)構(gòu)實現(xiàn)適用場景和性能可能不同。比如同樣是線性表,可能有多種存儲結(jié)構(gòu)的實現(xiàn)方式。比如順序表和鏈表(Arraylist,Linkedlist)它們的存儲結(jié)構(gòu)就不同，一個是順序存儲(數(shù)組)實現(xiàn)，一個是鏈式存儲(鏈表)實現(xiàn)。它關(guān)注的是計算機運行物理地址的關(guān)系。但通常同一類存儲結(jié)構(gòu)實現(xiàn)的一些數(shù)據(jù)結(jié)構(gòu)有一些類似的共同點和缺點(線性易查難插、鏈式易插難查等等)。

算法分析

上面講了數(shù)據(jù)結(jié)構(gòu)相關(guān)概念，下面對算法分析的一些概念進行描述。

算法的五個重要特征：有窮性、確定性、可行性、輸入、輸出。這些從字面意思即可理解，其中有窮性強調(diào)算法要有結(jié)束的時候不能無限循環(huán);而確定性是每條指令有它意義，相同的輸入得到相同的輸出;可行性是指算法每個步驟經(jīng)過若干次執(zhí)行可以實現(xiàn);輸入是0個或多個輸入(可0);輸出是1個或多個輸出(一定要有輸出)。

而一個好的算法，通常更要著重考慮的是效率和空間資源占用(時間復雜度和空間復雜度)，通常復雜度更多描述的是一個量級程度而很少用具體數(shù)字描述。

空間復雜度

概念：是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))

空間復雜度其實在算法的衡量占比是比較低的(我們經(jīng)常使用犧牲空間換時間的數(shù)據(jù)結(jié)構(gòu)和算法)，但是不能忽視空間復雜度中重要性。無論在刷題還是實際項目生產(chǎn)內(nèi)存都是一個極大額指標。對于Java而言更是如此。本身內(nèi)存就大，如果采用的存儲邏輯不太好會占用更多的系統(tǒng)資源，對服務(wù)造成壓力。

而算法很多情況都是犧牲空間換取時間(效率)。就比如我們熟知的字符串匹配String.contains()方法，我們都知道他是暴力破解，時間復雜度為O(n^2),不需要借助額外內(nèi)存。而KMP算法在效率和速度上都原生暴力方法，但是KMP要借助其他數(shù)組(next[])進行標記儲存運算。就用到了空間開銷。再比如歸并排序也會借助新數(shù)組在遞歸分冶的適合進行逐級計算，提高效率，但增加點影響不大的內(nèi)存開銷。

當然，算法的空間花銷最大不能超過jvm設(shè)置的最大值，一般為2G.(2147483645)如果開二維數(shù)組多種多維數(shù)據(jù)不要開的太大，可能會導致heap OutOfMemoryError。

時間復雜度

概念：計算機科學中，算法的時間復雜度是一個函數(shù)，它定性描述了該算法的運行時間。這是一個關(guān)于代表算法輸入值的字符串的長度的函數(shù)。時間復雜度常用大O符號表述，不包括這個函數(shù)的低階項和首項系數(shù)。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。

時間復雜度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

常見時間復雜度：對于時間復雜度，很多人的概念是比較模糊的。下面舉例子說明一些時間復雜度。

O(1): 常數(shù)函數(shù)

• a=15

O(logn): 對數(shù)函數(shù)

• for(int i=1;i
• 還有典型的二分查找，拓展歐幾里得，快速冪等算法均為O(logn)。屬于高效率算法。

O(n): 線性函數(shù)

• for (int i=0;i
• 比較常見，能夠良好解決大部分問題。

O(nlogn):

• for (int i=1;i
• 常見的排序算法很多正常情況都是nlogn，比如快排、歸并排序。這種算法效率大部分也還不錯。

O(n^2)

• for(int i=0;i
• 其實O(n^2)的效率就不敢恭維了。對于大的數(shù)據(jù)O(n^2)甚至更高次方的執(zhí)行效果會很差。

當然如果同樣是n=10000.那么不同時間復雜度額算法執(zhí)行次數(shù)、時間也不同。

降低算法復雜度有些會靠數(shù)據(jù)結(jié)構(gòu)的特性和優(yōu)勢，比如二叉排序樹的查找，線段樹的動態(tài)排序等等，這些數(shù)據(jù)結(jié)構(gòu)解決某些問題有些非常良好的性能。還有的是靠算法策略解決，比如同樣是排序，冒泡排序這種笨而簡單的方法就是O(n2),但快排、歸并等聰明方法就能O(nlogn)。要想變得更快，那就得掌握更高級的數(shù)據(jù)結(jié)構(gòu)和更精巧的算法。

時間復雜度計算時間復雜度計算一般步驟：1、找到執(zhí)行次數(shù)最多的語句; 2、計算語句執(zhí)行的數(shù)量級 ; 3、用O表示結(jié)果。并且有兩個規(guī)則：

加法規(guī)則：同一程序下如果多個并列關(guān)系的執(zhí)行語句那么取最大的那個,eg:

T(n)=O(m)+O(n)=max(O(m),O(n));  
T(n)=O(n)+O(nlogn)=max(O(n),O(nlogn))=O(nlogn); 

乘法規(guī)則：循環(huán)結(jié)構(gòu)，時間復雜度按乘法進行計算,eg：

T(n)=O(m)*O(n)=O(mn) 
T(n)=O(m)*O(m)=O(m^2)(兩層for循環(huán)) 

當然很多算法的時間復雜度還跟輸入的數(shù)據(jù)有關(guān)，分為還會有最優(yōu)時間復雜度(可能執(zhí)行次數(shù)最少時)，最壞時間復雜度(執(zhí)行次數(shù)最少時)，平均時間復雜度，這在排序算法中已經(jīng)具體分析，但我們通常使用平均時間復雜度來衡量一個算法的好壞。

數(shù)據(jù)結(jié)構(gòu)與算法學習

捋過數(shù)據(jù)結(jié)構(gòu)與算法基本概念的介紹，在學習數(shù)據(jù)結(jié)構(gòu)與算法方面，個人把經(jīng)典的數(shù)據(jù)結(jié)構(gòu)與算法學習過程步驟寫在下面，希望能給大家一個參考：

數(shù)據(jù)結(jié)構(gòu)

• 單鏈表(帶頭結(jié)點、不帶頭結(jié)點)設(shè)計與實現(xiàn)(增刪改查)，雙鏈表設(shè)計與實現(xiàn)
• 棧設(shè)計與實現(xiàn)(數(shù)組和鏈表)，隊列設(shè)計與實現(xiàn)(數(shù)組和鏈表)
• 二叉樹概念學習，二叉樹前序、中序、后序遍歷遞歸、非遞歸實現(xiàn) ，層序遍歷
• 二叉排序樹設(shè)計與實現(xiàn)(插入刪除)
• 堆(優(yōu)先隊列、堆排序)
• AVL(平衡)樹設(shè)計與實現(xiàn)(四種自旋方式理解實現(xiàn))
• 伸展樹、紅黑樹原理概念理解
• B、B+原理概念理解
• 哈夫曼樹原理概念理解(貪心策略)
• 哈希(散列表)原理概念理解(幾種解決哈希沖突方式)
• 并查集/不相交集合(優(yōu)化和路徑壓縮)
• 圖論拓撲排序
• 圖論dfs深度優(yōu)先遍歷、bfs廣度優(yōu)先遍歷
• 最短路徑Dijkstra算法、Floyd算法、spfa算法
• 最小生成樹prim算法、kruskal算法
• 其他數(shù)據(jù)結(jié)構(gòu)線段樹、后綴數(shù)組等等

經(jīng)典算法

• 遞歸算法(求階乘、斐波那契、漢諾塔問題)
• 二分查找
• 分治算法(快排、歸并排序、求最近點對等問題)
• 貪心算法(使用較多，區(qū)間選點問題，區(qū)間覆蓋問題)
• 常見動態(tài)規(guī)劃(LCS(最長公共子序列) LIS(最長上升子序列)背包問題等等)
• 回溯算法(經(jīng)典八皇后問題、全排列問題)
• 位運算常見問題(參考劍指offer和LeetCode問題)
• 快速冪算法(快速求冪乘、矩陣快速冪)
• kmp等字符串匹配算法
• 一切其他數(shù)論算法(歐幾里得、拓展歐幾里得、中國剩余定理等等)

相信看完這篇文章，你應(yīng)該對數(shù)據(jù)結(jié)構(gòu)與算法有個不錯的認知。數(shù)據(jù)結(jié)構(gòu)與算法有著非常密切的關(guān)聯(lián)，數(shù)據(jù)結(jié)構(gòu)是為了實現(xiàn)某種算法，算法是核心目的。學習數(shù)據(jù)結(jié)構(gòu)與算法之前，可以先參考書本或者博客先了解其功能，再研究其運行原理，再動手實戰(zhàn)(編寫數(shù)據(jù)結(jié)構(gòu)或者相關(guān)題目)這樣層次漸進，想要深入的學習數(shù)據(jù)結(jié)構(gòu)與算法光理解是不行的，需要有大量代碼實戰(zhàn)才可。并且這條路是沒有止境的，活到老，學到老，刷到老。

原文鏈接：https://mp.weixin.qq.com/s/RSZmRRihze7gllewXmh1ng