樓下大爺看完直呼簡單！時間復雜度和空間復雜度【資料結構】（文章排版引起極大舒適）-有解無憂

《內卷資料結構》第一章：時間復雜度和空間復雜度

前言：

今年上半年更新的C語言系列教程《維生素C語言》在今年九月份已順利完結，感謝大家的關注和支持！目前擬定主要更新C/C++方向的博客，次要更新Python和刷題題解，現在正式開啟資料結構專欄，通過本人不斷地輸出，排版的美觀性個人認為已經近乎完美了，盡可能最大限度地讓讀者在觀看文章內容時引起極大舒適，此外，增添了黃色記號筆劃重點部分，以圖文并茂的形式進行展現內容，減少閱讀的枯燥性，目前展現的排版我個人認為是比較滿意的，本人將會繼續改進，呈現出更多優質的博客給大家，

資料結構專欄我將分為初階資料結構和高階資料結構來寫，高階資料結構考慮到要使用到C++，我會在期間更新C++系列教程，當然，只會比之前出的C語言教程更好，

值得一提的是，資料結構初階部分將用C語言進行講解，如果需要學習或復習C語言可以訂閱專欄進行學習，本專欄已完結，請放心收藏！

🔗 訂閱專欄：《維生素C語言》

本章為資料結構篇的第一章，將簡單介紹下資料結構和演算法的基本概念，著重講解時間復雜度和空間復雜度，介紹大O漸進表示法，千里之行始于足下，讓我們一起開始吧！

一、資料結構前言

0x00 何為資料結構

【百度百科】資料結構（Data Structure）是帶有結構特性的資料元素的集合，它研究的是資料的邏輯結構和資料的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的演算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構型別，簡而言之，資料結構是相互之間存在一種或多種特定關系的資料元素的集合，即帶“結構”的資料元素的集合，“結構”就是指資料元素之間存在的關系，分為邏輯結構和存盤結構，

📚 定義：資料結構（Data Structure）是計算機存盤、組織資料的方式，指相互相之間存在一種或多種特定關系的資料元素的集合，

? 學習資料結構有什么意義？

🔑 資料結構就是有些專案在實作程序中，我們需要在記憶體中把資料存盤起來：陣列（雖然方便但是擴容比較麻煩）、鏈表（用指標鏈接起來）、樹（查找）、哈希表……等等，

0x01 何為演算法

【百度百科】演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出，如果一個演算法有缺陷，或不適合于某個問題，執行這個演算法將不會解決這個問題，不同的演算法可能用不同的時間、空間或效率來完成同樣的任務，一個演算法的優劣可以用空間復雜度與時間復雜度來衡量，

📚 定義：演算法（Algorithm），即定義良好的計算程序，它取一個或一組的值輸入，并產生出一個或一組的值作為輸出，簡單來說，演算法就是一系列的計算步驟，用來將輸入資料轉化成輸出結果，

? 為什么要學習演算法？

🔑 舉個簡單的例子：抖音的推薦演算法，比如記錄用戶經常在哪個視頻停留時間長從而進行分析，你經常看什么視頻，它就會給你推送什么，不難看出，演算法已經無處不在了，

0x02 學習建議

? 如何才能學好資料結構和演算法？

💡 ~~多讀書少看報，少吃零食多睡覺~~（bushi），多敲代碼多刷題，要注重畫圖和思考！等資料結構學習得差不多了，推薦刷《劍指offer》和《程式員代碼面試指南》上的題：

👉 猛戳！劍指Offer【牛客網】

👉 猛戳！LeetCode【力扣官網】

二、演算法效率

0x00 衡量演算法好壞的方法

? 如何衡量一個演算法的好壞？看代碼是否簡潔？

💬 比如對于以下斐波那契數列：

long long Fib(int n) {
    if (n < 3) {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

🤔 不難發現，斐波那契數列使用遞回方式實作時代碼非常簡潔，但代碼簡潔就一定好嗎？我們該如何去衡量他的好壞呢？讓我們帶著問題我們繼續往下看，

0x01 演算法的復雜度

📚 介紹：演算法在撰寫成可執行程式后，運行時需要耗費 時間資源 和 空間資源（即記憶體資源），因此，衡量一個演算法的好壞一般是從 "時間" 和 "空間" 兩個維度來衡量的，即時間復雜度和空間復雜度：

① 時間復雜度：主要衡量一個演算法的運行快慢，

② 空間復雜度：主要衡量一個演算法運行所需要的額外空間，

💡 須知：在計算機發展早期，計算機的存盤容量很小，所以大家都很在乎空間復雜度，但是經過計算機行業的迅速發展，現在電腦記憶體越來越大了，記憶體也越來越便宜了，所以我們如今不再關注 "空間" ，已經不需要再特別關注一個演算法的空間復雜度了，

摩爾定律（英特爾創始人之一戈登·摩爾的經驗之談）：其核心內容為，集成電路上可以容納的晶體管數目在大約每經過18個月便會增加一倍，換言之，處理器的性能每隔兩年翻一倍，它一定程度揭示了資訊技術進步的速度，現代計算機發展就像開了掛一樣地快，

👉 想了解猛戳：【百度百科】摩爾定律

🔺 注：復雜度在校招中的考察很多，校園招聘在筆試演算法題和面試中都會考察對復雜度的計算和理解！此外，考研也是必考復雜度，

二、時間復雜度

0x00 時間復雜度的概念

📚 時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式（這里的函式時數學里的函式，數學里面帶有未知數的函式運算式），它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上來說其實是不能算出來的，只有你把你的程式放在機器上跑起來才能知道耗費了多少時間，但是把每個演算法都跑一遍是非常不現實的事，所以就產生了時間復雜度這樣的分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

? 該如何計算時間復雜度呢？

🔑 簡單來說就是：找到某潭訓本陳述句與問題規模 N 之間的數學運算式，就是算出了該演算法的時間復雜度，

💬 例子：計算一下 Func1 中 ++count 陳述句總共執行了多少次？

void Func1(int N) {
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; j++) {
            ++count;
        }
    }

    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }

    int M = 10;
    while (M--) {
        ++count;
    }

    printf("%d\n", count);
}

🔑 Func1 執行的基本操作次數如下：

${\color{Magenta} F}({\color{Blue} N}) = {\color{Blue} N}^2 + 2*{\color{Blue} N} + 10$

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

💡 N 越大，后兩項對結果的影響就越小，所以我們也不需要精確的計算出結果，算個大概就可以了，所以這里我們將使用 大O漸進表示法 進行表示，

0x01 大O漸進表示法

【百度百科】大O符號（Big O notation）是用于描述函式漸進行為的數學符號，更確切地說，它是用另一個（通常更簡單的）函式來描述一個函式數量級的漸近上界，在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩余項，在計算機科學中，它在分析演算法復雜性的方面非常有用，

📚 定義：大O符號是用于描述函式漸進性為的數學符號，

📚 推導大O階方法：

① 用 常數1 取代運行時間中的所有加法常數，

② 在修改后的運行次數函式中，只保留最高階項，

③ 如果最高階 存在且不是1 ，則去除與這個專案相乘的常數，最后得到的結果就是大O階，

🔑 使用大O漸進表示法后，Func1 的時間復雜度為 O(N^2) ：

${\color{Magenta} F}({\color{Blue} N}) = {\color{Blue} N}^2 + 2*{\color{Blue} N} + 10$

↓

${\color{Red} O}({\color{Blue} N}^2)$

N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

（看到大O就知道這里面的值不是準確的值，而是大概值）

📌 注意事項：

① 一般情況下，時間復雜度計算式未知數都是用的 N，但是也可以是 M、K、X 等等其他的，如果出現其他字母（非N）的情況情況我們可以這么表示：

如果 M 遠大于 N → O(M)

如果 N 遠大于 M → O(N)

M 和 N 差不多大 → O(M + N)

② O(1) 不是代表演算法運行一次，而是 "常數次" ，

💡 通過上面的例子，我們發現大O漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，

📚 另外有些演算法的時間復雜度存在最好情況、平均情況、最壞情況：

① 最好情況：任意輸入規模的最小運行次數（下界）
② 平均情況：任意輸入規模的期望運行次數
③ 最壞情況：任意輸入規模最大的運行次數（上界）

時間復雜度是一個悲觀的預期，當一個演算法隨著輸入不同、時間復雜度不同，做一個悲觀的預期，看最壞的情況！

💬 例子：在一個長度為N的陣列（下面例題中會出現，先提前講個大概）

① 最好情況：1 次找到

② 最壞情況：N 次找到

③ 平均情況：N/2 次找到

📚 在實際中，一般情況下我們主要關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N) ，當然，這不是絕對的！比如希爾排序很少出現最壞的情況，所以有時候我們也會看平均情況，

0x02 時間復雜度計算的實體

💬 實體1：計算 Func2 的時間復雜度

void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N ; ++ k) {
        ++count;
    }

    int M = 10;
    while (M--) {
        ++count;
    }
    
    printf("%d\n", count);
}

💡 答案：O(N)

🔑 決議：基本操作執行了 2N+10 次，通過推導大O階方法知道，時間復雜度為 O(N) ，因為當N越大，對10的影響就越小，所以+10省略，并且2N根據第三條規則（前面講了），相乘時不是1時系數忽略，所以使用大O漸進法表示結果如下：

${\color{Magenta} F}({\color{Blue} N}) = 2{\color{Blue} N}+10$

↓

${\color{Red} O}({\color{Blue} N})$

我們帶到題里再看一遍規則：

① 用常數1取代運行時間中的所有加法常數，

② 在修改后的運行次數函式中，只保留最高階項，

③ 如果最高階存在且不是1 ，則去除與這個專案相乘的常數，

? 為什么不算 ++k ？

🔑 我們不需要算的那么精確，我們只需要算回圈的次數，指的是演算法邏輯走了多少次，而不是程式走了多少條指令，所以我們不需要考慮 ++k ，

💬 實體2：計算 Func3 的時間復雜度

void Func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; ++ k) {
        ++count;
    }
    
    for (int k = 0; k < N ; ++ k) {
        ++count;
    }

    printf("%d\n", count);
}

💡 答案：O(M + N)

🔑 決議：基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(M+N），一般情況下時間復雜度計算時未知數用的是N，但是也可以用其他未知數表示（前面講過），所以使用大O漸進法表示結果如下：

${\color{Red} O}({\color{Blue} M}+{\color{Blue} N})$

為了加深印象，我們再看一遍：

一般情況下，時間復雜度計算式未知數都是用的 N，但是也可以是 M、K、X 等等其他的，如果出現其他字母（非N）的情況情況我們可以這么表示：

如果 M 遠大于 N → O(M)

如果 N 遠大于 M → O(N)

M 和 N 差不多大 → O(M + N)

💬 實體3：計算 Func4 的時間復雜度

void Func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; ++ k) {
        ++count;
    }

    printf("%d\n", count);
}

💡 答案：O(1)

🔑 決議：基本操作執行了10次，通過推到大N階的方法，時間復雜度為O(1) ，值得注意的是，這里的 "1" 是常數次而不是代表演算法運行1次，所以使用大O漸進法表示結果如下：

${\color{Magenta} F}({\color{Blue} N}) = 100$

↓

${\color{Red} O}(1)$

💬 實體4：計算 strchr 的時間復雜度

// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );

💡 答案：O(N)

🔑 決議：基本操作執行最好1次，最壞N次，因為時間復雜度一般取最壞，所以時間復雜度為O(N) ，使用大O漸進法表示結果如下：

$worst: {\color{Magenta} F}({\color{Blue} N}) = ({\color{Blue} N}/2)$

↓

${\color{Red} O}({\color{Blue} N})$

💬 實體5：計算 BubbleSort 的時間復雜度

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
    int exchange = 0;
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0) {
            break;
        }
    }
}

💡 答案：O(N^2)

🔑 決議：基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2) ，冒泡排序，前一個比后一個大就交換，這兩個回圈雖然嵌套在一起，但是里面的回圈不是n，外面的回圈也不是n，而是end，它是在變化的，{ N-1 N-2 N-3 ... 1 } ，所以他是個等引數列，使用大O漸進法表示結果如下：

${\color{Magenta} F}({\color{Blue} N})={\color{Blue} N}*({\color{Blue} N}-1)/2$

↓

${\color{Red} O}({\color{Blue} N}^2)$

💬 實體6：計算 BinarySearch 的時間復雜度

int BinarySearch(int* a, int n, int x) {
    assert(a);
    int begin = 0;
    int end = n - 1;
    while (begin < end) {
        int mid = begin + ((end-begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }

    return -1;
}

💡 答案：O(logN)

🔑 決議：基本操作執行最好1次，最壞O(logN)次，時間復雜度為O(logN），使用大O漸進法表示結果如下：

${\color{Red} O}(log{\color{Blue} N})$

? 記不得log是什么了？log是對數：

在這里，我不得不吹一下二分查找了，真的是個非常牛掰的演算法！

N個數中查找大概查找次數

1000 10

100W 20

1億 30

......

在中國14億人口中查找一個人，最多只要31次就可以了！當然，二分查找查找物件前提是有序的，

💬 實體7：計算遞回版階乘 Fac 的時間復雜度

long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}

💡 答案：O(N)

🔑 決議：通過計算分析發現基本操作遞回了N次，時間復雜度為O(N) ，使用大O漸進法表示結果如下：

${\color{Red} O}({\color{Blue} N})$

📚 遞回演算法：遞回次數 * 每次遞回呼叫次數

💬 實體8：計算遞回版斐波那契數 Fib 的時間復雜度

long long Fib(size_t N) {
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

💡 答案：O(2^N)

🔑 決議：通過計算分析發現基本操作遞回了2^N次，時間復雜度為O(2^N) ，使用大O漸進法表示結果如下：

${\color{Red} O}(2^{\color{Blue} N})$

三、空間復雜度

0x00 空間復雜度的概念

📚 空間復雜度的定義：空間復雜度也是一個數學運算式，是對一個演算法在運行程序中臨時占用存盤空間大小的量度，空間復雜度并不是程式占用了多少bytes的空間，前面在介紹演算法復雜度的時候就提到了如今我們已經不再關注 "空間" ，所以關注程式占用多少byte的空間是沒有太大意義的，空間復雜度算的是變數的個數！此外，空間復雜度的計算規則基本和時間復雜度沒有什么區別，同樣也使用 大O漸進表示法，

📌 注意事項：函式運行時所需要的堆疊空間（即存盤引數、區域變數和一些暫存器資訊等）在編譯期間就已經確定好了，因此空間復雜度主要是通過函式在運行的時候顯式申請的額外空間來決定，

0x01 時間復雜度計算的實體

💬 實體1：計算 BubbleSort 的空間復雜度

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
    int exchange = 0;
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0) {
            break;
        }
    }
}

💡 答案：O(1)

🔑 決議：使用了常數個額外空間，所以空間復雜度為 O(1) ，

${\color{Red} O}(1)$

💬 實體2：計算 Fibonacci 的空間復雜度

// 回傳斐波那契數列的前n項
long long* Fibonacci(size_t n) {
    if(n==0)
        return NULL;

    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; ++i) {
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }

    return fibArray;
}

💡 答案：O(N)

🔑決議：malloc 動態開辟了N個空間，空間復雜度為 O(N)

${\color{Red} O}({\color{Blue} N})$

💬 實體3：計算遞回版階乘 Fac 的空間復雜度

long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}

💡 答案：O(N)

🔑 決議：遞回呼叫了N次，開辟了N個堆疊幀，每個堆疊幀使用了常數個空間，空間復雜度為O(N) ，

${\color{Red} O}({\color{Blue} N})$

四、常見復雜度對比

0x00 常見的復雜度

一般演算法常見復雜度表
$92366$	${\color{Red} O}(1)$	常數階
$3N+4$	${\color{Red} O}({\color{Blue} N})$	線性階
$3N^2+4N+5$	${\color{Red} O}({\color{Blue} N}^2)$	平方階
$3log(2)n+4$	${\color{Red} O}(log{\color{Blue} N})$	對數階
$2n+3nlog(2)n+14$	${\color{Red} O}({\color{Blue} N}log{\color{Blue} N})$	nlogn階
$n^3+2n^2+4n+6$	${\color{Red} O}({\color{Blue} N}^3)$	立方階
$2^N$	${\color{Red} O}(2^{\color{Blue} N})$	指數階