怎么理解時間復(fù)雜度和空間復(fù)雜度

本篇內(nèi)容介紹了“怎么理解時間復(fù)雜度和空間復(fù)雜度”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

我們經(jīng)?？梢钥吹竭@樣的描述：軟件=數(shù)據(jù)結(jié)構(gòu)+算法，可見算法基礎(chǔ)對于一個程序員的重要性。算法中，有兩個基本概念：時間復(fù)雜度和空間復(fù)雜度。

• 時間復(fù)雜度：描述算法執(zhí)行消耗的時間，時間越短，時間復(fù)雜度越低，算法越優(yōu)秀；

• 空間復(fù)雜度：描述算法執(zhí)行所占用的內(nèi)存空間，占用內(nèi)存越少，空間復(fù)雜度越低，算法越優(yōu)秀；

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

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

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

比如，一個普通的循環(huán)：

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

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

再比如，一個雙層循環(huá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;
}

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

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

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

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

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

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

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

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

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

常見的時間復(fù)雜度量級：

• 常數(shù)階O(1)

• 對數(shù)階O(logN)

• 線性階O(n)

• 線性對數(shù)階O(nlogN)

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

• 指數(shù)階(2^n)

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

如果想在一個數(shù)組中找到一個數(shù)，最簡單的方法就是循環(huá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;
}

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

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

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

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

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

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