怎么理解時間復雜度和空間復雜度

本篇內容介紹了“怎么理解時間復雜度和空間復雜度”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

我們經常可以看到這樣的描述：軟件=數據結構+算法，可見算法基礎對于一個程序員的重要性。算法中，有兩個基本概念：時間復雜度和空間復雜度。

• 時間復雜度：描述算法執行消耗的時間，時間越短，時間復雜度越低，算法越優秀；

• 空間復雜度：描述算法執行所占用的內存空間，占用內存越少，空間復雜度越低，算法越優秀；

因此，時間復雜度和空間復雜度是評價一個算法性能的主要指標。那么如何計算一個算法的時間復雜度和空間復雜度呢？

簡單理解，計算時間復雜度就是評估一個算法完成后執行了多少行代碼，也就是算法所消耗的時間，但是該如何用數學的方式其表示出來呢？

假設現在有個一個算法需要執行n次運算，我們用T(n)表示，n即表示算法的規模（比如n=10時，循環輸出10次Hello World；n=100時，循環輸出100次Hello World）。如果假設存在一個函數f(n)，表示隨著n的變化，算法需要執行的次數，當T(n)=O(f(n))，那么O(f(n))即為算法的時間復雜度。

比如，一個普通的循環：

public int calc(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
    return total;
}

當n越大，循環的次數越多，那么耗費的時間也就越大，也就是f(n)隨著n線性增長。那么該算法的執行時間T(n)=O(n)，即時間復雜度為O(n)。

再比如，一個雙層循環：

public int calc(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += j;
        }
    }
    return total;
}

外層循環每循環一次，內層循環就循環了n次，那么代碼總循環次數就是n*n。那么該算法的執行時間T(n)=O(n^2) ，即時間復雜度為O(n^2)。

一般來說，時間復雜度是用來評估隨著n的增大，算法執行需要消耗時間的增速，而不是精確計算消耗的時間，事實上也無法精確計算。既然是評估，那么f(n)函數我們只需要保留對消耗時間影響最大的因子即可。

例如，有一個f(n)=2*n^3函數，系數2對f(n)函數的增速影響就不大，所以該算法的時間復雜度T(n)=O(n^3)，即忽略常量系數對增速的影響。

再比如，在一個沒有循環的代碼塊里，只有三行輸出代碼：

public void print() {
    System.out.println("Hello 河先森");
    System.out.println("Hello 河先森");
    System.out.println("Hello 河先森");
}

即T(n)=3，是一個常數，而常數對增速的影響是可以忽略的，那么該代碼塊的時間復雜度就是O(1)。

再來看一個例子，計算下面代碼塊的時間復雜度：

public void print(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            System.out.println("Hello 河先森");
        }
    }
}

當i=0時，內層循環了n次，當i=1時，內層循環了n-1次，以此內推，當i=n-1時，內層循環了1次。那么總的循環次數T(n)=n+(n-1)+(n-1)+...+1=n(n+1)/2=n^n/2+n/2，忽略常數項和對增速影響不大的因子，只保留影響最大的因子，那么該算法的時間復雜度即為O(n^2)。

常見的時間復雜度量級：

• 常數階O(1)

• 對數階O(logN)

• 線性階O(n)

• 線性對數階O(nlogN)

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

• 指數階(2^n)

以上算法時間復雜度中，隨著n的增大，f(n)增速越快，說明算法的效率越低。即算法耗費的時間O(1) < O(logN) < O(n) < O(nlogN) < O(n2) < O(n3) < O(n^k) < O(2^n)。

如果想在一個數組中找到一個數，最簡單的方法就是循環遍歷：

public boolean search(int m) {
    int[] arr = new int[]{3, 5, 7, 1, 2, 6, 4, 9};
    for (int i = 0; i < arr.length; i++) {
        if (m == arr[i]) {
            return true;
        }
    }
    return false;
}

如果要查找的是數是數組的第一個數（本例子中的3），那么只需要一次循環就能找到，時間復雜度為O(1)。但是如果要查找的數在數組最后位置（本例中的9），那么必須要經過arr.length次循環，時間復雜度為O(n)，n為數組的長度。那么這段代碼代碼塊的時間復雜度到底是多少呢？

一般在沒有特殊說明的情況下，時間復雜度都是指最壞的時間復雜度，因為沒有比這更壞的情況了。所以這段代碼塊的時間復雜度為O(n)。

時間復雜度描述的是算法消耗時間趨勢，同理，空間復雜度則是描述算法在運行時臨時內存消耗的趨勢，一般用 S(n) 來定義，記作S(n)=O(fn)。

至于評價算法的具體好壞，就要具體情況具體分析了。有時我們會拿時間換空間，有時會去拿空間換時間，有時則需要同時考慮時間和空間復雜度。

總之，具體問題具體分析，但是我們一定要理解時間復雜度和空間復雜度的分析過程。

“怎么理解時間復雜度和空間復雜度”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！