文末有投票哦~~

前言

兄弟，想一起學習演算法嗎？想一起變強嗎？想畢業的時候在演算法方面吊打面試官嗎？想成為刷題狂人嗎？

快來聯系我，一起互相監督，一起征服力扣~~

我的伙伴，刷題四天王（自己封的）：

英雄大哥

吒老二

扣三

菜鳥的我

那還等啥！演算法那還不得趕緊學起來！這一激動我這包整的河南話都彪出來了，

一、什么是演算法

什么是演算法？我們為什么要學演算法？演算法是為了什么才出現的？演算法是怎么從解決一個問題慢慢到解決一個體系的問題的？

想要學習演算法，如果你要求不高，你可以不學這個，你只需要知道怎么用，如何用，什么地方用就可以了~

但是如果你對演算法想有深入的了解，那么這些你是需要知道的，

1.1 緒論

想必大家都聽過這樣一句話：資料結構+演算法=程式

你可能會說：屁嘞，我不會資料結構與演算法，我也照樣寫程式，我只能說：能說出來這話，一看你就是個新手！

你了解什么是資料結構嗎？你了解什么是演算法嗎？不要把它們看得那么高大上，他們的原本定義其實很簡單的~~

資料結構：

提一嘴基礎知識，在編程語言中，資料是資訊的載體，而資料又分為值型別和參考型別，值型別無非就是整數，實數，復數等，而參考型別就是那些陣列，字串，集合圖片，音樂等，

有位老哥說過：任何資料都可以使用資料結構表現出來，其實意思就是，資料結構就是存盤資料的結構體，

其實資料結構的定義就是這么簡單，不要看的太高

演算法：

一個程式，有一種書本上的描述：解決一個問題除了要有一個資料結構來表示和組織資訊外，還需要一系列步驟來完成問題的解決方案，

當然了，第一個逗號前面的那當然就是資料結構了，那后面的一系列步驟其實說的就是演算法，

也可以稱為：操作資料結構的方法；或者稱為：解決問題的方案，

那么看完這兩個概念，你是否對資料結構與演算法有一個了解了呢？你是否還會說，我不會資料結構與演算法也能寫程式了呢？

有點模糊也沒關系，我來帶你看幾個例子，你就明白了~~

案例：

例子1 HelloWorld：

HelloWorld也能當資料結構與演算法的例子？？！沒錯，沒看錯，他能！他能！！

java代碼：

public class Hello{
  /*
      在這里Hello和World就是兩個資料結構
      將兩個資料結構用+拼接起來，就是演算法
   */
 public static void main(String[] a){
     System.out.println("Hello"+"World"); 
 }
}

Python代碼：

print("Hello"+"World")

同理

例子2 兩個數字相加：

輸入兩個數字，輸出兩個數字的和

Java代碼：

public class Hello{
 public static void main(String[] a){
     System.out.println(sumTwo(5,6)); 
 }
 public static int sumTwo(int a, int b){
     return a+b;
 }
}

這里面沒有資料結構，只有時間，也有演算法，演算法就是a+b

Python代碼：

def sumTwo(a:int,b:int)->int:
 return a+b

例子3 兩數之和（來真的了啊！）：

給你一個非空陣列，和一個目標值，從陣列中找出兩個元素使其的和與目標值相同，并回傳一個長度為2的陣列裝這兩個值對應的下標，只允許一個元素使用一次

————源于力扣第一題，簡單難度

Java代碼：

public class Hello{
public static void main(String[] a){
  System.out.println(); 
}
public static TwoSum(int[] nums1, int[] nums2, int target){
  /*
    最容易想到的，也是沒學過系統學習過演算法的人的方法
    嵌套回圈：
    遍歷nums1，再遍歷nums2，然后求和，與目標值做判斷
    當然，想法很簡單，卻會出錯，因為還要考慮元素只用到一遍
  */
  for (int i=0;i<nums.length;i++){
      for (int j=0;j<nums.length;j++){
          if (i!=j){
              if (nums[i]+nums[j]==target){
                  return new int[]{i, j};
              }
          }
      }
  }
  return null;
}
}

這里面就用到了一個資料結構，叫做陣列，這里的演算法就是將新陣列求出來的程序！

Python代碼：

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
     for i in range(len(nums)):
         for j in range(len(nums)):
             if i==j:
                 continue
             elif nums[i]+nums[j]==target:
                     return [i, j]

當然，例3的方法是很簡陋的，更簡單的方法還有哈希法和二分法，在這道題中，哈希法的時間復雜度是O(n)，二分法的時間復雜度為O(nlogn)

感興趣的話，可以看看我的這一篇博客：零基礎的我刷力扣一周后，總結了點東西

這三個例子大概也能讓你對什么是資料結構與演算法有一個大致的了解了，那么接著看吧~

二、為什么要學演算法

既然知道了演算法是什么，那么你知道為什么要學習演算法嗎？

有人可能會說：因為我想在找作業的時候更有競爭力，更有話語權，所以我來學演算法！這個當然沒錯，面向加薪學習~~

當然了，除了這個，也沒什么別的辦法能夠令人瘋狂了吧~~興趣？有，很少的~

那么為什么公司喜歡會演算法的人呢？換句話說，為什么會演算法的人會更吃香呢？

因為公司運行你的代碼是需要機器的，而機器也是分價錢的，如果你的演算法很糟糕，那就會讓公司的機器運行起來占用CPU資源多，擬人化一下那就是會很吃力，而且運行你得代碼會更耗費時間，

而如果你會演算法，甚至演算法很好，那么你的演算法就會讓機器如釋重負，甚至跑的更快！

想一想，機器同樣的價錢，你會演算法能夠讓機器干更多事，那公司肯定要你啊！別說工資，那一個機器都好貴的，

而演算法的出現也是因為先有了問題，之前也說過演算法是什么了，就是一個問題的解決方案，所以我們的演算法是為了解決問題才出現的，

三、演算法的特性

當然一個問題都是可以由多個演算法解決的，俗話說，無規矩不成方圓，

那么不同的演算法是不是得有相同的規則，或者說相同的特性，才能約束演算法，不能任意一種演算法就可以解決問題，

打個比方，就用曹沖稱象這個例子吧，為了不浪費大家的腦子，我決定就說的簡單一點，

現有大象一頭，需要知道大象有多重，但是秤太小，無法精準測量，

請你設計一個演算法來計算大象的重量，

曹沖的方法：把象放到大船上，在水面所達到的地方做上記號，再讓船裝載其它東西，稱一下這些東西,那么比較下就能知道了，

方法1：我把大象切碎，一塊一塊量

方法2：造一個超大的秤，專門用來秤大象的重量

你覺得方法1和方法2怎么樣？先不急著回答，我們先看看演算法的這幾個性質，

1. 有窮性

一個演算法必須要有一個明確的終止條件來控制處理程序的終止，或者說結束，

什么意思呢？就是你的演算法至少要有一個終止條件，或者說能夠在特定時間內終止，并計算出結果，要不然你的方法有什么意義呢？

2. 確定性

你的演算法的每個步驟都是有明確的目的，不能有別的意思，

就拿上面的例子，你說要把大象切碎，不能切著切著，我還是再造個秤吧，

3. 可行性

你的演算法的沒一個步驟都是可以被機器或者人執行的，

就像曹沖的方法一樣，是切實可行的，而像方法12，則多少有點不切實際了，

4. 正確性

你的演算法所計算的結果是能夠用來解決這個問題的，

不能說你的演算法無法解決問題，那樣你的演算法也是毫無意義的，

那么，在看完這四個特性后你怎么回答上面的問題呢？

當然，答案我也在特性里面說了出來，還不知道答案的，面壁思過去！

四、演算法的分析

那么講了這么多，我們怎么判斷我們的程式是好是壞呢？那就是時間復雜度和空間復雜度，

是不是感覺這兩個名詞好難理解？沒事，他其實也不難，

1. 時間復雜度

所謂時間復雜度就是演算法執行的時間，而時間復雜度可以由兩種方式：

• 計算程式實際運行時間
• 計算程式相對運行時間

我們知道，即使是同一種演算法，在不同的編程語言，不同的機器，不同的環境索引行的實際時間也是不一樣的，

所以第一種方式，就不是很銀杏化！那么就只能是第二種方法了來判斷我們的程式是否得到了優化~~

而時間復雜度又分為三種，最優情況，最劣情況，平均情況，而這個情況是由問題來決定的~

這三種情況我就不多說啦~看名字就知道了

時間復雜度統一使用O(x)來表示，也是俗稱的大O表示法，而時間復雜度的大小與問題有關，

比方說：

1. 我給你三個數，你把他們三個從小到大排序，時間復雜度是O(3)，也可以說是 O(1)
2. 我給你10**100個數，你把他們從小到大排序，時間復雜度是O(10**100)，也可以近似取到O(1)
3. 我給你幾個數，你把他們從小到大排序，時間復雜度為O(n)

那么為什么改了一下題目，時間復雜度就不一樣了呢？因為1，2是確定的值，不會受到外部影響而改變，所以只需要回圈那么多次，不會改變所以時間復雜度是O(1)；而3不一樣，他給的值是不確定的，所以需要回圈n次，時間復雜度就是O(n)

當然這個也是可以根據問題改變的，那就是對特定的值使用特定的演算法，比如二分法，遞回的時間復雜度就是O(logn)，而O(n)是大于O(logn)的

而如果需要嵌套回圈，那么可能是O(n**2)或者O(nlogn)，

常見的時間復雜度按照從小到大的順序排列有：O(1)，O(logn)，O(n)，O(nlogn)，O(n**2)，O(2**n)，O(n!)

2. 空間復雜度

根據演算法在執行程序所使用的存盤空間，分為堆區和堆疊區，當然還有別的區，

而堆疊區中存放著變數名，堆區中存放著變數名指向的值，這么說可能不好理解，那就畫個圖吧~~

誒😱😨叭叭了這么多，好像還沒到點上！

稍安勿躁嘛~~

這就來空間復雜度啦~

其實和時間復雜度差不多，我們使用常數，實數，或者對陣列，字串進行原地修改的時候，空間復雜度就是O(1)，因為沒有開辟新的空間

而如果是新建一個字串，陣列就是需要新開辟一個陣列或者字串空間，所以空間復雜度為O(n)

五、演算法

關于一些生活中常見的演算法…

這里不講代碼，只講原理！

1. 貪婪演算法

在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的演算法 ，

他也叫貪心演算法，

舉個栗子：

你去超市買東西，買了十三塊錢的東西

你拿了一百塊錢，給收銀員，收銀員會給你找零錢

貪婪演算法就是：

先找你一張50的，再找你一張20的，再10的，再5的，再1的，再1的

當然這也是一般收銀員會選擇的方法，通過找給你最少張的紙幣，找給你所需要的錢

這就是貪婪演算法

貪婪演算法所能解決的問題的特性：

• 該問題至少有一個最優的解決方案，只有這樣，才可能為解決問題構造候選方案集合，在前面的例子中候選方案集合就是不同面值的紙幣組成的紙幣集，

• 隨著問題的求解將建立另外兩個集合，-一個集合(假設為集合a)由已經被選出并符合問題要求的候選解組成，另一個集合(假設為集合b)由已經被選出但并不符合問題要求的候選解組成，

• 集合a最終要包含問題的解答，在集合a中未出現解答時，問題的候選解集合中至少還要剩余一個候選解，

貪婪演算法的有點事簡單，直觀，容易實作，但是缺點也很明顯，那就是他會認為當前選擇是滿足條件的就進行下一個，而不管當前操作是否會對下一操作產生影響，

2. 分治法

- 分治法就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并，
- 說簡單點就是：把一個復雜的問題分成幾個簡單的問題，如果分的還不夠簡單，那就接著分，然后再把各個簡單的問題解答，最終的答案就是所有簡單問題答案的并集

舉個栗子：

給你一個有序陣列和一個目標值，請找出這個元素的下標

我們使用二分查找法

Java代碼：

public class ErFen{
 public static void main(String[] a){

 }
 public static int Defg(int[] nums, int target){
     int start = 0;
     int end = 0;
     int mid = 0;
     for (int i=0;i<nums.lenrth;i++){
         mid = (start+end)/2;
         if (nums[mid]>target) end = mid;
         else start = mid+1;
     }
     return mid;
 }
}

Python代碼：

def Defg(nums:list, target:int)->int:
 start = 0
 end = 0
 mid = 0
 for i in range(len(nums)):
     mid = (start + end) //2
     if nums[mid]>target: end = mid
     else: start = mid
 return mid

看不懂？沒關系，看這是什么！！！大寶貝！——LeetCode刷題278-簡單-第一個錯誤版本

分治法所能解決的問題的特性：

• 整個問題可以分解為兩個或者多個較小的問題

• 對每個子問題的求解類似于對整個問題的求解

• 如果子問題的規模或者難度仍舊很大，那就繼續使用分治法

分治法的難度較高，技巧性較高，需要使用者對問題有著透徹的理解，效率也不高，

但是能解決很多復雜的問題，

3. 動態規劃

在現實生活中，有一類活動的程序，由于它的特殊性，可將程序分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個程序達到最好的活動效果，因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態，又影響以后的發展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個程序的一潭訓動路線．這種把一個問題看作是一個前后關聯具有鏈狀結構的多階段程序就稱為多階段決策程序，這種問題稱為多階段決策問題，在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最優化的程序為動態規劃方法

這個演算法是極其難以理解的，就算理解，代碼也很難敲出來，

而也可以這么理解，動態規劃的塑像是與分治法的思想相反的，如果說分治法這種吧一個問題分解成多個簡單問題的方法叫做自上而下的方法，那么動態規劃就是一種自下而上的解決方法，

而動態規劃也不會出現貪婪演算法那種當前操作最優而不再以下一操作的情況，

舉個栗子：

計算二項式Cnm的值

使用楊輝三角可以根據當前二項式生成更簡單的二項式

而不會重復生成更簡單的相同的二項式

所以才叫動態規劃

動態規劃解決的問題的特性：

• 演算法要解決大量重復的作業，計算大量重復的數值，
• 至少有一 些新的數值可以通過已經計算出的數值組合出來，
• 問題要具有一定的規模，這樣動態規劃演算法的好處才可凸顯出來，
• 使用分治法劃分 子問題時，子問題之間的關系界限不清，相互交叉，一個子問題的求解與多個已經解決的子問題有關，

優點是效率高，缺點是太難了~~

有好多人都不會用，包括某菜雞博主~~

4. 回溯法

回溯法是一種優化的窮舉法， 所謂窮舉法就是窮舉問題的所有可能性，直到發現解決問題的最佳解為止，當然利用窮舉法可以解決很大一部分的實際問題，但由窮舉法的實作程序可知它所花費的資源是相當多的，使用窮舉法進行徹底的搜索徹底的比較，要以大量的運算為基礎，而大量的運算勢必要花費大量的時間，有時這種消耗是計算機也承擔不起的，所以用窮舉法解決問題往往是不實際的，

說白了還是窮舉法~~

舉個栗子：

你站在一顆形狀類似于一個思維導圖的頭結點

你想查看某個尾結點，但是計算機可看不到，所以使用回溯法

回溯法就是讓你先沿著最左邊的一直走

一直沿著最左邊，直到尾結點，你發現不是自己想要的

回傳上一個父節點，再往右走，不是，回到父節點的父節點

繼續往右，然后再往左…

回圈往復，直到找到你想要的尾結點才停止，

回溯法解決的問題的特性：

• 問題可以劃分為幾個不相關的子問題
• 幾個字問題有類似的解決方案
• 如果子問題還可以劃分，就繼續劃分

缺點：由于是窮舉法，所以效率極低

5. 概率演算法

概率演算法允許演算法在執行程序中隨機地選擇下一個計算步驟，在很多情況下，演算法在執行程序中面臨選擇時，隨機性選擇比最優選擇省時，因此概率演算法可以在很大程度上降低演算法的復雜度，

他也叫，隨機演算法，

說直白了他就是碰運氣，但是總能碰到正確的答案，但是得不到精準的答案，

只有在某些場合才會使得效率增大，

舉個栗子：

比如說某國的總統選舉

不讓所有人進行投票選舉

而是隨機找一些人進行民意調查

最后統計結果

支持率搞得就是新的國家總統

效率是不是提高了！

你可以說結果是正確的，但不能說結果是精準的

優點是在某種情況下能使得解決問題的效率大大提高，缺點是不是所有的問題都適用，

結語

希望閱讀完我這篇文章，能夠讓你對資料結構與演算法打下基礎，

我是布小禪，一位初入IT界的萌新，希望多多關照~~

興趣是最好的老師，堅持是不變的真理，
學習不要急躁，一步一個腳印，踏踏實實的往前走，
每天進步一點點，榷訓月累之下，再回頭看看，你就會發現自己已經變得很厲害了，