算法+ 數(shù)據(jù)結(jié)構(gòu) = 程序

導讀

1.1 為什么要學習數(shù)據(jù)結(jié)構(gòu)與算法

    很多人認為學習數(shù)據(jù)結(jié)構(gòu)與算法只是為了應付面試话浇，在日常的開發(fā)中基本上沒有使用的機會挽鞠，也有一些同學去刷題牵署，但發(fā)現(xiàn)有時候這些題目一看就會一問就費的局面漏隐。甚至有一些的同學看到數(shù)據(jù)結(jié)構(gòu)和算法這一詞時內(nèi)心直接就是抵觸的。

這里很大的一部分原因是因為你沒有真正的去了解數(shù)據(jù)結(jié)構(gòu)奴迅，你有想過為什么大廠都要求數(shù)據(jù)結(jié)構(gòu)與算法嗎青责？為什么技術(shù)過關(guān)了但是總會掛在算法這一關(guān)？

學習數(shù)據(jù)結(jié)構(gòu)與算法不僅僅是學習其中的數(shù)組取具，鏈表脖隶，隊列，堆棧暇检，樹产阱，圖等經(jīng)典的結(jié)構(gòu)，也不僅僅是學習應付面試的算法块仆。

其實數(shù)據(jù)結(jié)構(gòu)是考驗你的基本功是否扎實的重要環(huán)節(jié)之一构蹬，最重要的是你要學習一種思想：如何把現(xiàn)實問題轉(zhuǎn)化為計算機語言的表示。

算法+ 數(shù)據(jù)結(jié)構(gòu) = 程序

本篇文章將介紹數(shù)據(jù)結(jié)構(gòu)中的基礎概念悔据，了解基礎概念之后會配套的做一些相關(guān)的練習題加深對其的理解庄敛。希望能對你得到一些幫助。

這個專題也會不斷的向內(nèi)添加內(nèi)容科汗，如有圖片或者描述錯誤的地方或者講解不清楚的地方還請各位同學及時指出藻烤，我加以改正。

目前已完成數(shù)據(jù)結(jié)構(gòu)的基本概念 相關(guān)算法題會在編輯算法章節(jié)時陸續(xù)補充進來肛捍。感謝關(guān)注隐绵。

1.2 什么是數(shù)據(jù)結(jié)構(gòu)與算法

    [數(shù)據(jù)](https://baike.baidu.com/item/數(shù)據(jù)/5947370)結(jié)構(gòu)是[計算機](https://baike.baidu.com/item/計算機/140338)存儲、組織[數(shù)據(jù)](https://baike.baidu.com/item/數(shù)據(jù))的方式拙毫。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的[數(shù)據(jù)元素](https://baike.baidu.com/item/數(shù)據(jù)元素/715313)的集合依许。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲[效率](https://baike.baidu.com/item/效率/868847)缀蹄。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索[算法](https://baike.baidu.com/item/算法/209025)和[索引](https://baike.baidu.com/item/索引/5716853)技術(shù)有關(guān)峭跳。

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

1. 線性結(jié)構(gòu)：線性表（數(shù)組膘婶、鏈表、隊列蛀醉、棧悬襟、哈希表）

2. 樹型結(jié)構(gòu)：二叉樹、AVL樹拯刁、紅黑樹脊岳、B樹、堆垛玻、Trie割捅、哈夫曼樹、并查集

3. 圖形結(jié)構(gòu)：鄰接矩陣帚桩、鄰接表

    算法（Algorithm）是指解題方案的準確而完整的描述亿驾，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制 
   

算法包括：遞推法账嚎、遞歸法莫瞬、窮舉法、貪心算法郭蕉、分治法疼邀、動態(tài)規(guī)劃法、迭代法召锈、分支界限法檩小、回溯法

一. 算法基本概念

    算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令烟勋，算法代表著用系統(tǒng)的方法描述解決問題的策略機制

一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。

特征：

1. 有窮性(Finiteness)：算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止筐付。
2. 確切性(Definiteness)： 算法的每一步驟必須有確切的定義卵惦。
3. 輸入項(Input):：一個算法有0個或多個輸入，以刻畫運算對象的初始情況瓦戚，所謂0個輸入是指算法本身定出了初始條件沮尿。
4. 輸出項(Output)：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果较解。沒有輸出的算法是毫無意義的畜疾。
5. 可行性(Effectiveness)：算法中執(zhí)行的任何計算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個計算步驟都可以在有限時間內(nèi)完成（也稱之為有效性）印衔。

1.1 時間復雜度

    算法的時間復雜度是指執(zhí)行算法所需要的計算工作量啡捶。也就是說程序需要執(zhí)行的次數(shù)

大O表示法

一般用大O表示法來描述負責度，它表示的是數(shù)據(jù)規(guī)模為n對應的復雜度

• 忽略常數(shù)奸焙、系數(shù)瞎暑、低階

  執(zhí)行次數(shù)	復雜度	非正式術(shù)語
  12	O(1)	常數(shù)階
  2n+3	O(n)	線性階
  4n^2+2n+6	O(n^2)	平方階
  4log2n+25	O(logn)	對數(shù)階
  3n+2nlog3n+15	O(nlogn)	nlogn階
  4n3+3n2+n+12	O(n^3)	立方階
  2^n	O(2^n)	指數(shù)階

img

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

1.2 空間復雜度

    空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度彤敛，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 了赌。而一般的遞歸算法就要有O(n)的空間復雜度了墨榄，因為每次遞歸都要存儲返回信息。一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量)勿她。

二. 數(shù)據(jù)結(jié)構(gòu) - 線性結(jié)構(gòu)（）

圖文介紹：
帶你了解數(shù)據(jù)結(jié)構(gòu)與算法袄秩。附leetcode練習
算法 - 十大經(jīng)典排序算法(動圖演示)