【時間復雜度和空間復雜度】簡單理解與學習-有解無憂

前言

學習演算法之前，我們需要先搞懂時間復雜度和空間復雜度，顧名思義，時間復雜度和空間復雜度是一個判斷演算法好壞的一個標準，時間復雜度就相當于運行代碼花費的時間，空間復雜度則代表代碼所占用的記憶體空間，在實際的作業環境中，自然是運行快，占用空間少的代碼更具優勢，就像一道數學題它本身有多種解法，我們都偏向去使用更簡單、更巧妙的方法，

時間復雜度

首先呢，在一個演算法中，陳述句執行的次數稱之為陳述句頻度或時間頻度，記為T(n)，并且一個演算法花費的時間是和時間頻度成正比的，n是問題的規模，n不斷變化時，T(n)也會不斷變化，為了更清晰地明白這個變化所呈現出來的規律，我們就引入了時間復雜度，注意：T(n)=O(f(n)),稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度，

演算法中重復執行地次數是問題規模n的某個函式，我們記為T(n)，并使用某個輔助函式f(n)，當n趨于無窮大時，T(n)/f(n)趨于某個不等于零的常數，則稱f(n)為T(n)的同數量級函式，記作T(n)=O(f(n))，

我們不僅要知道什么是時間復雜度，并要會如何計算出某個演算法的時間復雜度，

常數階O(1)

在不同演算法中，只要演算法中陳述句執行次數為一個常數，則它的時間復雜度就為O(1)

1 public static void way01(int n){
2     int a=0;
3     int b=1;
4     int c=a+b;
5     System.out.println(c);
6 }

注意：只要代碼不存在回圈、遞回等回圈類呼叫，那么無論演算法中執行多少條陳述句，只要為常數，那它的時間復雜度就為常數階O(1).

線性階O(n)

1 public static void way02(int n){
2     int a=0;
3     for(int i=0;i<n;i++){
4         a+=i;
5     }
6     System.out.println(a);
7 }

以上，我們假設一條陳述句執行時間為t，則T(n)=t+t*n,而在演算法中有一個原則，就是常量可以忽略不計，那么t+tn---->tn---->n，則可記為O(n)，并且不同演算法，它們的時間復雜度也可能是相同的，例如T(n)=n+2與T(n)=3n+4,由于常量可以忽略，則變成O(n+2)=O(n),O(3n+4)=O(3n)=O(n),則它們的時間復雜度均為O(n)，

平方階O(n^2)

與線性階類似，比如T(n)=n²+n+2與T(n)=3n²+2n+4,分別表示O(n²+n)、O(3n²+2n)------>O(n(n+2))、O(3n(n+2/3))------>O(n²)、O(3n²)----->均為O(n²)，

對數階O(logn)

對數階相較而言有些麻煩，不過也好理解，下面通過例子解釋：

1 public static void way03(int n){
2     int a=1;
3     while(a<=n){
4         a*=2;
5     }
6 }

假設while回圈中回圈x次，則2^x=n,x=log₂n,則T(n)=1+log₂n，同理，當a*=3、a*=4……時，那么T(n)=log₃n,T(n)=log₄n……，且T(n)=log₃n=log₃2*log₂n,則他們的時間演算法復雜度為O(log₂n),實際表達中，我們直接記為O(logn)，

線性對數階O(nlogn)

與對數階類似

1 public static void way04(int n){
2     int a=1;
3     for(int i=0;i<n;i++){
4         while(a<=n){
5             a*=2;
6         }
7     }
8 }

顯然，O(n)=1+nlogn=nlogn

以上就是時間復雜度的一些簡單理解和計算，這里面當然還會有其他更深入的知識，這里就不過多贅述了，

空間復雜度

空間復雜度是指演算法在計算機執行時所需存盤空間的度量，記為S(n)=O(f(n))

演算法所占用的空間主要分為三大類：一、演算法本身占用的空間，二、演算法的輸入輸出資料所占用的空間，三、運行程序中所臨時占用的空間

這里討論的是除正常占用記憶體開銷外的輔助存盤單元，

空間復雜度的分析與時間復雜度類似，當一個演算法的空間復雜度為一個常數（他不隨n的改變而改變）時，記為O（1），若演算法里面出現陣列、串列、堆疊等它們會隨著n的改變而改變占用記憶體空間的大小，比如一維陣列nums,它的長度為n，則其空間復雜度就記為O(n)，其他型別同理，

補充：

當一個演算法中出現T(n)=O(n²)+O(n)+O(1),則選擇復雜度最高的那一個，即T(n)=O(n²),如果出現了兩個復雜度相同的，比如T(n)=O(n)+O(m)+O(1)，則記為它們之和O(m+n)，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509123.html

標籤：其他

上一篇：Gimbal Lock歐拉角死鎖問題

下一篇：NebulaGraph 的云產品交付實踐