數據結構

我是一個“棧”

• 計算機世界中存儲和組織數據的
  下面來介紹四種不同的數據存儲方式
• 數組
  存儲方式：按順序存儲在連續的內存中
  獲取方式：只需要提供位置索引
  注意事項：只能保存相同類型的數據
  特點：讀取容易，刪除和插入困難。
• 鏈表
  存儲方式：不連續的空間，一個節點包含數據和指向下一個節點的指針。
  獲取方式：從第一個開始找，直到找到你需要的數據
  特點：尋址困難，刪除和插入容易
• 棧
  原則：先進后出
• 隊列
  原則：先進先出

時間復雜度：
用O(n)表示， 是一個函數，定性的描述了一個算法的運行時間
從執行次數T(n)可以知道一個算法的時間復雜度
存在常數c，使得當N>=c時T(N)<=f(N),表示為T(n) = O(f(n))
隨著輸入大小n的增加，算法執行需要的時間的增長速度可以用f(n)表示
從T(n)=>O(n)
T(n)= 常數，O(n)=1,
選擇高次項

比如 T(n) = n^3 + n^2 + 29，此時時間復雜度為 O(n^3)。

忽略與最高階相乘的常數
從算法通過分析和數學運算得到T(n)
1.對于一個循環，假設循環體的時間復雜度是O(n),循環次數是m，則這個循環的時間復雜度是O(nm)
2.多個循環，循環體的時間復雜度是O(n)，各循環次數a,b,c...，O(n) = O(nabc...)。分析的時候要從里向外分析
3.順序執行的算法，總的時間復雜度等于最大的復雜度
4.條件判斷語句，總的時間復雜度等于時間復雜度最大的路徑的復雜度
快速排序的時間復雜度
1.最好是O(nlogn)
2.最差是O(n2)

O(n)：代表數據量增大幾倍，耗時也增大幾倍。比如常見的遍歷算法

O(logn)：當數據增大n倍時，耗時增大logn倍（這里的log是以2為底的，比如，當數據增大256倍時，耗時只增大8倍，是比線性還要低的時間復雜度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256個數據中查找只要找8次就可以找到目標

O(nlogn)：n乘以logn，當數據增大256倍時，耗時增256*8=2048倍。這個復雜度高于線性低于平方。歸并排序就是O(nlogn)的時間復雜度

O(1)：最低的時空復雜度，也就是耗時與輸入數據大小無關，無論輸入數據增大多少倍，耗時/耗空間都不變。 哈希算法就是典型的O(1)時間復雜度，無論數據規模多大，都可以在一次計算后找到目標（不考慮沖突的話)

空間復雜度：
描述一個算法所需要的內存空間

遞歸算法：一個過程或函數在其調用和說明中有直接或間接調用自身的一種方法，通常是把一個復雜大型的問題轉化為與原問題相似的規模較小的問題來求解。遞歸策略只需要少量的程序就可以描述出解題過程所需要的多次重復計算，大大減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。

一般來說，遞歸需要有邊界條件，遞歸前進段和遞歸返回段，當邊界條件不滿足時，遞歸前進，當邊界條件滿足時，遞歸返回。

構成遞歸所需要的條件：

1.子問題與原始問題為同樣的事，且更為簡單；

2.不能無限調用，需有個出口，化簡為非遞歸狀況處理。

斐波那契數列是典型的遞歸案例。

遞歸算法相對于循環來說有一定的性能問題。如果遞歸的特別深，還有可能會導致棧溢出。

遞歸算法的設計步驟:

1.確定遞歸公式

2.確定邊界（終了）條件

典型例題：

快速排序算法：取出無序數列的第一個值，然后通過比較將比該值小的元素放到該值的前方，將比該值大的元素放到該值的后方，然后再次對前半部分和后半部分無序的數列進行上述操作。

快速排序算法的平均復雜度是O(nlogn),最糟糕時復雜度是O(n^2)

比較插入、冒泡、歸并、快速等不同的排序算法的優劣。從額外空間消耗，平均時間復雜度和最差時間復雜度等方面去比較他們的優缺點。

轉載于:https://www.cnblogs.com/kehaoran/p/11101439.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的数据结构和算法基础概述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。