前言

<>重要性

* 數(shù)據(jù)結(jié)構(gòu)與算法是程序員內(nèi)功體現(xiàn)的重要標(biāo)準(zhǔn)之一，而數(shù)據(jù)結(jié)構(gòu)的也應(yīng)用在各個(gè)方面，更有程序=數(shù)據(jù)結(jié)構(gòu)+算法這個(gè)等式存在。各個(gè)中間件開(kāi)發(fā)者，架構(gòu)師
。他們都在努力的優(yōu)化中間件、項(xiàng)目結(jié)構(gòu)以及算法提高運(yùn)行效率降低內(nèi)存占用
。并且數(shù)據(jù)結(jié)構(gòu)中也是蘊(yùn)含模型以及面向?qū)ο蟮乃枷耄莆諗?shù)據(jù)結(jié)構(gòu)對(duì)邏輯思維處理抽象能力有很大提升。。
<>數(shù)據(jù)結(jié)構(gòu)



<>概念

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

* 簡(jiǎn)言之，數(shù)據(jù)結(jié)構(gòu)是一系列的存儲(chǔ)結(jié)構(gòu)按照一定執(zhí)行規(guī)則、配合一定執(zhí)行算法
所形成的高效的存儲(chǔ)結(jié)構(gòu)。在我們所熟知的關(guān)系數(shù)據(jù)庫(kù)、非關(guān)系數(shù)據(jù)庫(kù)、搜索引擎存儲(chǔ)、消息隊(duì)列等都是比較牛的大型數(shù)據(jù)結(jié)構(gòu)良好的運(yùn)用。這些數(shù)據(jù)結(jié)構(gòu)應(yīng)用不僅僅考慮到內(nèi)存范圍結(jié)構(gòu)設(shè)計(jì)。還考慮實(shí)際os、網(wǎng)絡(luò)等
其他因素。
* 而對(duì)于數(shù)據(jù)結(jié)構(gòu)與算法這個(gè)專(zhuān)欄。我們程序員更改掌握的首先是在內(nèi)存中運(yùn)行的抽象的數(shù)據(jù)結(jié)構(gòu)。是一個(gè)相對(duì)比較單一的數(shù)據(jù)結(jié)構(gòu)類(lèi)型，比如線性結(jié)構(gòu)、樹(shù)、圖等等.
<>相關(guān)術(shù)語(yǔ)


用戶信息表users

idnamesex
001 bigsai man
002 smallsai man
003 菜虛鯤 woman
users的pojo對(duì)象
class users { //略 int id; String name; String sex; } //list和woman是數(shù)據(jù) List<users
>list;//數(shù)據(jù)對(duì)象list List<users>woman;//數(shù)據(jù)對(duì)象woman list.add(new users(001,"bigsai",
"man"));//添加數(shù)據(jù)元素 一個(gè)users由（001，bigsai，man）三個(gè)數(shù)據(jù)項(xiàng)組成 list.add(new users(002,
"smallsai","man"));//數(shù)據(jù)元素 list.add(new users(003,"菜虛鯤","woman"));//數(shù)據(jù)元素 woman.
add(list.get(2));//003,"菜虛鯤","woman"三個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的一個(gè)數(shù)據(jù)元素
* 數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合總稱。
上述表中的三條用戶信息的記錄就是數(shù)據(jù)(也可能多表多集合)。這些數(shù)據(jù)一般都是用戶輸入或者是自定義構(gòu)造完成。當(dāng)然，還有一些圖像、聲音也是數(shù)據(jù)。
* 數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)構(gòu)成！可認(rèn)為是一個(gè)pojo對(duì)象、或者是數(shù)據(jù)庫(kù)的一條記錄。比如菜虛鯤那條記錄就是一個(gè)數(shù)據(jù)元素。
* 數(shù)據(jù)項(xiàng)： 而構(gòu)成用戶字段/屬性的有id、name、sex等，這些就是數(shù)據(jù)項(xiàng).數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的最小不可分割字段
?？梢钥醋饕粋€(gè)pojo對(duì)象或者一張表(people)的一個(gè)屬性/字段的值。
* 數(shù)據(jù)對(duì)象：是相同性質(zhì)數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。比如上面的users表、list集合、woman
集合都是數(shù)據(jù)對(duì)象。單獨(dú)一張表，一個(gè)集合都可以是一個(gè)數(shù)據(jù)對(duì)象。
* 數(shù)據(jù)類(lèi)型
* 原子類(lèi)型：其值不可再分的類(lèi)型。比如int，char，double，float等。
* 結(jié)構(gòu)類(lèi)型：其值可以再分為若干成分的數(shù)據(jù)類(lèi)型。比如結(jié)構(gòu)體構(gòu)造的各種結(jié)構(gòu)等。
* 抽象數(shù)據(jù)類(lèi)型(ADT)：抽象數(shù)據(jù)類(lèi)型（ADT）是一個(gè)實(shí)現(xiàn)包括儲(chǔ)存數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)以及實(shí)現(xiàn)基本操作的算法。使得只研究和使用它的結(jié)構(gòu)而不用考慮它的實(shí)現(xiàn)細(xì)節(jié)
成為可能。比如我們使用Arraylist。二叉樹(shù)等等只需要new
一個(gè)而不需要去具體考慮他的內(nèi)部實(shí)現(xiàn)方式。只需要了解他的api和性質(zhì)即可。其實(shí)各個(gè)框架的思想也是這樣，對(duì)數(shù)據(jù)、接口進(jìn)行封裝、繼承使得我們只需要會(huì)用而不需要弄清楚它的具體實(shí)現(xiàn)細(xì)節(jié)。
<>三要素

* 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)就是順序表、鏈表之類(lèi)。而非線性就是集合、樹(shù)、圖這些結(jié)構(gòu)。
* 存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像，也稱物理結(jié)構(gòu))，存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列(哈希)存儲(chǔ)。
* 數(shù)據(jù)的運(yùn)算：施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn),運(yùn)算的定義基于邏輯結(jié)構(gòu)，運(yùn)算的實(shí)現(xiàn)基于存儲(chǔ)結(jié)構(gòu)。
* 在這里容易混淆的是邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的概念。對(duì)于邏輯結(jié)構(gòu)，不難看得出邏輯
二字。邏輯關(guān)系也就是兩者存在數(shù)據(jù)上的關(guān)系而不考慮物理地址的關(guān)系。比如線性結(jié)構(gòu)和非線性結(jié)構(gòu)，它描述的是一組數(shù)據(jù)中的聯(lián)系方式和形式
，他針對(duì)的是數(shù)據(jù)。而存儲(chǔ)結(jié)構(gòu)就是跟物理地址掛鉤的。比如同樣是線性表,可能有多種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方式。比如順序表和鏈表
(Arraylist,Linkedlist)它們的存儲(chǔ)結(jié)構(gòu)就不同并且采用不同存儲(chǔ)結(jié)構(gòu)在不同場(chǎng)景計(jì)算機(jī)運(yùn)算次數(shù)和效率不同。它關(guān)注的是計(jì)算機(jī)物理地址與運(yùn)行具體實(shí)現(xiàn)方式。
<>算法分析



<>五個(gè)重要特性

* 至于算法的概念，傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)介紹都會(huì)有：有窮性、確定性、可行性、輸入、輸出。這些從字面意思即可理解。
* 而一個(gè)好的算法，通常更要著重考慮的是效率和空間資源占用。
<>算法效率的度量

通常復(fù)雜度更多描述的是一個(gè)量級(jí)程度而很少用具體數(shù)字描述。

<>空間復(fù)雜度

概念：是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))

*
空間復(fù)雜度其實(shí)在算法的衡量占比是比較低的，但是不能忽視
空間復(fù)雜度中重要性。無(wú)論在刷題還是實(shí)際項(xiàng)目生產(chǎn)內(nèi)存都是一個(gè)極大額指標(biāo)。對(duì)于java而言更是如此。本身內(nèi)存就大，如果采用的存儲(chǔ)邏輯不太好會(huì)占用更多的系統(tǒng)資源，對(duì)服務(wù)造成壓力。

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

*
當(dāng)然，你的時(shí)間算法的空間花銷(xiāo)最大不能超過(guò)jvm設(shè)置的最大值，一般為2G.(2147483645)如果開(kāi)二維數(shù)組多種多維數(shù)據(jù)不要開(kāi)的太大，可能會(huì)導(dǎo)致heap
OutOfMemoryError。

<>時(shí)間復(fù)雜度*

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

時(shí)間復(fù)雜度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) <O(n!) <
O(nn)

常見(jiàn)時(shí)間復(fù)雜度：對(duì)于時(shí)間復(fù)雜度，很多人的概念是比較模糊的。下面舉例子說(shuō)明一些時(shí)間復(fù)雜度。

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

* a=15
O(logn):?對(duì)數(shù)函數(shù)

* for(int i=1;i<n;i*=2)
分析：假設(shè)執(zhí)行t次使得i=n;有2t=n; t=log2n,為log級(jí)別時(shí)間復(fù)雜度為O(logn)。
* 還有二分查找，拓展歐幾里得，快速冪等算法均為O(logn)(曾記錄過(guò))。屬于高效率算法。
O(n):?線性函數(shù)

* for (int i=0;i<n;i++)
* 比較常見(jiàn)，能夠良好解決大部分問(wèn)題。
O(nlogn):

* for (int i=1;i<n;i++)
for (int j=1;j<i;j*=2)
* 常見(jiàn)的排序算法很多正常情況都是nlogn。
O(n2)

* for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
* 其實(shí)O(n2)的效率就不敢恭維了。對(duì)于大的數(shù)據(jù)O(n2)甚至更高次方的執(zhí)行效果會(huì)很差。
當(dāng)然如果同樣是n=10000.那么不同時(shí)間復(fù)雜度額算法執(zhí)行次數(shù)、時(shí)間也不同。

具體n執(zhí)行次數(shù)
O(1) 10000 1
O(log2n) 10000 14
O( n1/2) 10000 100
O(n) 10000 10000
O(nlog2n) 10000 140000
O(n2) 10000 100000000
O(n3) 10000 1000000000000
* 當(dāng)然有些復(fù)雜度靠先天結(jié)構(gòu)優(yōu)勢(shì)，比如樹(shù)的查找，線段樹(shù)的動(dòng)態(tài)排序等等。還有的是靠算法策略解決，比如同樣是排序，冒泡排序
的地位就略低，還有dp算法用動(dòng)態(tài)發(fā)現(xiàn)規(guī)律解決問(wèn)題。要想變得更快，那就得掌握更高級(jí)的數(shù)據(jù)結(jié)構(gòu)和更精巧的算法。
時(shí)間復(fù)雜度計(jì)算
時(shí)間復(fù)雜度計(jì)算一般步驟：

* 1、找到執(zhí)行次數(shù)最多的語(yǔ)句
2、計(jì)算語(yǔ)句執(zhí)行的數(shù)量級(jí)
3、用O表示結(jié)果
兩個(gè)規(guī)則：

* 加法規(guī)則： 同一程序下如果多個(gè)并列關(guān)系的執(zhí)行語(yǔ)句那么取最大的那個(gè)。
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)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算
eg：T(n)=O(m)*O(n)=O(mn)
·T(n)=O(m)*O(m)=O(m^2)(兩層for循環(huán))
其他：

* 當(dāng)然有些算法的時(shí)間復(fù)雜度還跟輸入的數(shù)據(jù)有關(guān)，分為還會(huì)有最優(yōu)時(shí)間復(fù)雜度(可能執(zhí)行次數(shù)最少時(shí))，最壞時(shí)間復(fù)雜度(執(zhí)行次數(shù)最少時(shí))，平均時(shí)間復(fù)雜度.這在后面的
排序算法會(huì)具體分析。
當(dāng)然，后面會(huì)一起學(xué)習(xí)一些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)和常見(jiàn)的算法，進(jìn)行復(fù)雜度剖析。至于緒論，就先介紹這些，下面會(huì)先介紹線性表和遞歸算法。

* 歡迎關(guān)注我的個(gè)人公眾號(hào)：bigsai? 關(guān)注回復(fù) 數(shù)據(jù)結(jié)構(gòu) 即可獲取精心準(zhǔn)備的資料一份(精心)
*

• ? 上一篇：基于可視化配置的日志結(jié)構(gòu)化轉(zhuǎn)換實(shí)現(xiàn)
• ? 下一篇：（二十四）c#Winform自定義控件-單標(biāo)題窗體