快速掌握算法時間復雜度與空間復雜度

前言

一個算法的優劣好壞,會決定一個程序運行的時間、空間。也許當小數據量的時候,這種影響并不明顯,但是當有巨量數據的時候,算法的好壞帶來的性能差異就會出天差地別。可以說直接影響了一個產品的高度和廣度。每個程序員都想用最優的算法解決問題,我們期待自己寫出的代碼是簡潔、高效的。但是如何評判一個算法的好壞呢?時間復雜度和空間復雜度就是一個很好的標準。

1. 時間復雜度

1.1 概念

執行算法所需要的計算工作量就是我們常說的時間復雜度。該值不一定等于接下來要介紹的基本執行次數。是一個大約的數值,具有統計意義。

1.2 基本執行次數T(n)

根據計算,得出的該算法在輸入數據量為n時的,實際執行次數。該值為準確的,具體的數值,有數學意義。

1.3 時間復雜度

根據基本執行次數,去除系數、常數項等得到的漸進時間復雜度。用大O表示法。也就是說,隨著數據量的劇增,不同常數項和系數,已經大致不能夠影響該算法的基本執行次數。常數項和系數對于計算時間復雜度無意義

1.4 舉例說明

  1. T(n) = 2: 該函數總共執行兩條語句,所以基本執行次數為2;時間復雜度為O(1): 該函數的基本執行次數只有常數項,所以時間復雜度為O(1)
void test(int n)
{
    int a;
    a = 10;
}
  1. T(n) = 2n: 該函數共循環n次,每次執行2條語句,所以基本執行次數為2n。時間復雜度舍棄系數,為O(n)
void test(int n)
{
    int cnt;
    for (cnt = 0; cnt < n; cnt++) {
        int a;
        a= 10;
    }
}
  1. T(n) = 2 * (1 + 2 + 3 + 4 + ... + n) + 1 = 2 * (1 + n) * n / 2 + 1 = n^2 + n + 1。因為共執行(1 + 2 + 3 + 4 + ... + n) 次循環,每次循環執行2條語句,所有循環結束后,最后又執行了1條語句,所以執行次數如上;時間復雜度為O(n^2),因為n和常數項1忽略,它們在數據量劇增的時候,對于執行次數曲線幾乎沒有影響了
void test(int n)
{
    int cnt1, cnt2;
    for (cnt1 = 0; cnt1 < n; cnt1++) {
        for (cnt2 = cnt1; cnt2 < n; cnt2++) {
            int a;
            a = 10;            
        }
    }
    a = 11;
}
  1. T(n) = 2 * logn 因為每次循環執行2條語句,共執行logn次循環;時間復雜度為O(logn),忽略掉系數2
void test(int n)
{
    int cnt;
    for (cnt = 1; cnt < n; cnt *= 2) {
        int a;
        a = 10;
    }
}
  1. T(n) = n * logn * 2 因為每次循環2條語句,共執行n * logn次循環;時間復雜度為O(nlogn),忽略掉系數2
void test(int n)
{
    int cnt1, cnt2;
    for (cnt1 = 0; cnt1 < n; cnt1++) {
        for (cnt2 = 1; cnt2 < n; cnt2 *= 2) {
            int a;
            a = 10;
        }
    }
}
  1. T(n) = 2 * n^3 因為每次循環2條語句,共執行n^3 次循環;時間復雜度為O(n^3),忽略掉系數2
void test(int n)
{
    int cnt1, cnt2, cnt3;
    for (cnt1 = 0; cnt1 < n; cnt1++) {
        for (cnt2 = 0; cnt2 < n; cnt2++) {
            for (cnt3 = 0; cnt3 < n; cnt3++) {
                int a;
                a = 10;
            }
        }
    }
}
  1. 斐波那契數列的遞歸實現,每次調用該函數都會分解,然后要再調用2次該函數。所以時間復雜度為O(2^n)
int test(int n)
{
    if (n == 0 || n == 1) {
        return 1;
    }
    return (test(n-1) + test(n-2));
}

1.5 時間復雜度比較

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

2. 空間復雜度

2.1 概念

一個算法所占用的存儲空間主要包括:

  • 程序本身所占用的空間
  • 輸入輸出變量所占用的空間
  • 動態分配的臨時空間,通常指輔助變量

輸入數據所占空間只取決于問題本身,和算法無關。我們所說的空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度,即第三項。通常來說,只要算法不涉及到動態分配的空間以及遞歸、棧所需的空間,空間復雜度通常為0(1)。

2.2 舉例說明

  1. S(n) = O(1).空間復雜度為O(1),因為只有a, b, c, cnt四個臨時變量。且臨時變量個數和輸入數據規模無關。
int test(int n)
{
    int a, b, c;
    int cnt;
    for (cnt = 0; cnt < n; cnt++) {
        a += cnt;
        b += a;
        c += b;
    }
}
  1. S(n) = O(n).空間復雜度為O(n),因為每次遞歸都會創建一個新的臨時變量a。且共遞歸n次。
int test(int n)
{
    int a = 1;
    if (n == 0) {
        return 1;
    }
    n -= a;
    return test(n);
}

3. 函數的漸進增長與漸進時間復雜度

在上面的例子中,我們通常都會舍棄掉系數和常數項。這是因為當輸入量劇增,接近正無窮時,系數和常數項已經不能夠影響執行次數曲線。不同的系數和常數項曲線會完全重合。我做了一個折線圖用來比較當輸入值n激增時,n^2 曲線和 2n^2 + 100 曲線。可以看到,當數據量劇增時,系數和常數項對于統計時間復雜度都不再有意義,兩條曲線幾乎完全重合。

4. 不同算法的時間復雜度 & 空間復雜度

下圖是我做的一個表格,整理了不同的排序算法的時間復雜度和空間復雜度供大家參考:

感謝大家的閱讀,大家喜歡的請幫忙點下推薦。后面會繼續出精彩的內容,敬請期待!


敬告:

本文原創,歡迎大家學習轉載

轉載請在顯著位置注明:

博主ID:CrazyCatJack

原始博文鏈接地址:http://www.jsfhjj.com/CrazyCatJack/p/12657097.html


CrazyCatJack
posted @ 2020-04-07 23:42  CrazyCatJack  閱讀(...)  評論(...編輯  收藏
最新chease0ldman老人