序言

溫馨提醒，想直接看正文的可以跳過本段哈，在上個月底作者終于結束了C語言的入門和深剖，對的，之前說過進階還在路上哈（寒假就有了哈），然后一直到現在才再次冒頭，絕對不是玩去了哈，我沒有偷懶哈，咳咳，當然也確實休息了兩天，跨年嘛不是（這絕對不是我去浪的借口咳咳），不過緊接著就是莽資料結構去了，在此之前是接觸了一點的，那時學完了順序表，鏈表，堆疊和佇列，然后消失的這幾天就再次復習了一下，真的是解決了當時很多的疑惑，識訓真的很多，當然也不是復習這一個原因，因為復習之前也把C語言理論是學完了，這也是理解更深一個很重要的原因哈，然后就一直往下學，至1月3日晚，作者完成了這2022的第一篇博客，其實開始是沒準備來寫的，本想著把資料結構快速過一遍再來寫博客的，但是可能一直看視頻而且用倍數吧，腦袋有點暈乎乎的，在佇列結束后就是二叉樹了，然后二叉樹又是比前面的更難一些，所以就準備第二天再去肝他，狀態會好點，然后就有了本篇文章，想了想，資料結構對于小白不像之前那么容易理解，而且作者也想去更加完善文章，提升一下文章的品質，而且準備一下寫一個大內容，比如鏈表就是一個單內容這樣，不要像之前的分篇去寫，當然之前是沒辦法哈，內容太多了，一起太雜了，而且關聯性也不是那么強，但是資料結構關聯性很強而且內容不是太多可能更多偏于理解（就目前覺得），所以就準備一大塊一大塊內容來寫哈，感覺應該挺不錯的，但是之后的更新速度應該會慢一點了，可能兩三篇一周吧？但是絕對精哈！當然也可能有一些其他的文章，但是資料結構更新應該是快也快不了太多吧，好像想說的也就這么多，讓我們一起加油吧！沖刺大廠，不負未來，不負你！

誰都不能阻擋你成為更優秀的人，

1. 資料結構前言

1.1. 什么是資料結構？

資料結構(Data Structure)是計算機存盤、組織資料的方式，指相互之間存在一種或多種特定關系的資料元素的集合，

1.2.什么是演算法？

演算法(Algorithm):就是定義良好的計算程序，他取一個或一組的值為輸入，并產生出一個或一組值作為輸出，簡單來說演算法就是一系列的計算步驟，用來將輸入資料轉化成輸出結果，

1.3.如何學好資料結構和演算法

3.1. 死磕代碼，磕成這樣就可以了（=，=哈哈）

3.2. 注意畫圖和思考

兩點都非常重要，如果要做一個好的程式員，資料結構的學習絕對是必不可少的哈！

2. 什么是時間復雜度和空間復雜度？

大家一般都是在各種演算法題目上面看見的，是一個限制條件，其實網上是有很多篇幅去講這個東西，但是其實很簡單，總結就是時間復雜度不看時間，看次數，空間復雜度不看空間看個數，

2.1. 演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率， 間效率被稱為時間復雜度，而空間效率被稱作空間復雜度，時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度

2.2. 時間復雜度的概念

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

即：找到某潭訓本陳述句與問題規模N之間的數學運算式，就是算出了該演算法的時間復雜度，

2.3. 空間復雜度的概念

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度，

空間復雜度不是程式占用多少byte空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計規則基本跟時間復雜度類似，也使用大O漸進表示法，

注意：函式運行時所需要的堆疊空間(存盤引數、區域變數、一些暫存器資訊等)在編譯期間已經確定好了，因此空間復雜度主要通過函式在運行時候顯示申請的額外空間來確定，

3. 如何計算常見演算法的時間復雜度？

3.1. 讓我們來舉個栗子（重點）

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法，

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，

這上面的時間復雜度就是N*N+2*N+10，但是如果N夠大，2*N和10就顯得很小，可以忽略不計，此時N*N非常大，所以時間復雜度就是O（N^2），

再說明，比如我們去N個數里面找一個數（沒有相同的），有三種情況，最好情況一次找到，平均情況N/2，最壞情況N次找到在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N) ，

1. 基本操作執行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)，

2. 基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)，（要注意N，M差距大不大）

3. 基本操作執行了10次，通過推導大O階方法，時間復雜度為 O(1)，（只要是只有準確的數字就是O（1））

4. 基本操作執行最好1次，最壞N次，時間復雜度一般看最壞，時間復雜度為 O(N)，

5. 基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)，

6. 基本操作執行最好1次，最壞O(logN)次，時間復雜度為 O(logN) ，ps：logN在演算法分析

中表示是底數為2，對數為N，有些地方會寫成lgN（其實是錯的，與數學有矛盾），

7. 基本操作遞回了N次，時間復雜度為O(N)，