2025年6月30日 星期一

演算法的逆襲:為何 O(N log N) 的排序,有時竟能擊敗 O(N) 的雜湊?

***此篇文章由 Gemini AI 產生*** ### **演算法的逆襲:為何 O(N log N) 的排序,有時竟能擊敗 O(N) 的雜湊?** 身為一個程式開發者,我們對時間複雜度(Big O)可說是瞭若指掌。O(N) 通常優於 O(N log N),這幾乎是我們優化程式碼時的金科玉律。但如果我告訴你,在某些情況下,一個 O(N log N) 的演算法,在實際執行時竟然能穩定地擊敗 O(N) 的對手,你會怎麼想? 這不是天方夜譚,而是在 LeetCode、專案優化、甚至面試中都可能遇到的真實場景。今天,就讓我們透過一個經典問題「最長和諧子序列 (Longest Harmonious Subsequence)」,來一場跨越 C++ 和 Python 的效能對決,揭開理論與現實之間的迷霧。 #### **戰場設定:最長和諧子序列** 問題很簡單:給定一個整數陣列 `nums`,找到其中最長「和諧子序列」的長度。所謂和諧子序列,是指該子序列中最大值與最小值的差,剛好為 1。 例如,對於 `nums = [1, 3, 2, 2, 5, 2, 3, 7]`,其最長和諧子序列是 `[3, 2, 2, 2, 3]`,由 2 和 3 組成,長度為 5。 解決這個問題,有兩種經典的思路: 1. **排序 + 滑動窗口 (Sorting + Sliding Window):** 先將陣列排序,然後用兩個指針 `l` 和 `r` 遍歷一次,找出符合條件的最長區間。時間複雜度是 O(N log N),主要瓶頸在排序。 2. **雜湊表計數 (Hash Map):** 用一個雜湊表(在 Python 中是 `dict` 或 `Counter`)來計算每個數字出現的頻率。然後遍歷雜湊表,找出 `x` 和 `x + 1` 的頻率總和的最大值。時間複雜度是 O(N),因為只需要遍歷陣列一次。 理論上,雜湊表法 (O(N)) 應該完勝排序法 (O(N log N))。讓我們來實際測試一下。 ----- ### **第一戰:C++ 的意外結局** 在 C++ 的世界裡,我們用 `std::sort` 和 `std::unordered_map` 來實現這兩種方法。 **方法一:排序 + 滑動窗口 (O(N log N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::ranges::sort(nums); int ans = 0; int l = 0; for (int r = 1; r < nums.size(); ++r) { while (nums[r] - nums[l] > 1) ++l; if (nums[r] - nums[l] == 1) ans = std::max(ans, r - l + 1); } return ans; } }; ``` **方法二:雜湊表 (O(N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::unordered_map freq; for (int num : nums) ++freq[num]; int ans = 0; for (const auto& [num, count] : freq) if (freq.count(num + 1)) ans = std::max(ans, count + freq.at(num + 1)); return ans; } }; ``` **驚人的結果:** 在多數的 LeetCode 測試案例中,**排序法的執行時間竟然比雜湊表法要短!** 這完全違背了我們對 Big O 的直覺。為什麼?答案藏在硬體底層。 #### **解密 C++:當快取為王 (Cache is King)** ##### **1. 記憶體存取模式:循序 v.s. 隨機** * **排序法**在排序完成後,其滑動窗口的操作是**循序存取 (Sequential Access)** 一塊連續的記憶體。這對 CPU 快取(Cache)極度友好。當 CPU 讀取 `nums[i]` 時,它會聰明地將 `nums[i+1]`, `nums[i+2]` 等鄰近資料一併載入到飛快的 L1/L2 快取中。下一次的存取幾乎是零延遲,因為資料早已在手邊。 * **雜湊表法**則完全不同。`freq[num]` 和 `freq[num + 1]` 在記憶體中的位置是透過雜湊函數計算得出的,它們幾乎肯定是**隨機分散 (Random Access)** 的。這會導致大量的**快取未命中 (Cache Miss)**,CPU 不得不頻繁地從慢速的主記憶體 (RAM) 中去抓取資料,效能因此大打折扣。 ##### **2. 隱藏的常數開銷** Big O 符號忽略了常數因子。`unordered_map` 的每次操作都伴隨著不小的開銷: * **雜湊計算:** 需要時間。 * **碰撞處理:** 無法避免,會帶來額外尋找成本。 * **記憶體分配:** 每個鍵值對都可能需要一次動態記憶體分配,這比 `vector` 的整塊分配慢得多。 在 C++ 這種「貼近硬體」的語言中,演算法與硬體(特別是 CPU 快取)的互動方式,往往比單純的理論複雜度更能決定最終效能。在這裡,排序法贏在它優雅而高效的記憶體存取模式。 ----- ### **第二戰:Python 的情勢逆轉** 現在,我們將戰場轉移到 Python。 **方法一:排序 + 滑動窗口 (O(N log N))** ```python class Solution: def findLHS(self, nums: List[int]) -> int: nums.sort() l = 0 ans = 0 for r in range(len(nums)): while nums[r] - nums[l] > 1: l += 1 if nums[r] - nums[l] == 1: ans = max(ans, r - l + 1) return ans ``` **方法二:`Counter` 雜湊表 (O(N))** ```python from collections import Counter class Solution: def findLHS(self, nums: List[int]) -> int: freq = Counter(nums) ans = 0 for num, count in freq.items(): if num + 1 in freq: ans = max(ans, count + freq[num + 1]) return ans ``` **預料之中的結果:** 在 Python 環境下,**`Counter` 雜湊表法輕易地擊敗了排序法**,完美符合 Big O 的理論預期。 為什麼情勢完全逆轉了?答案在於 Python 的語言特性。 #### **解密 Python:直譯器的代價與 C 語言的捷徑** ##### **1. 直譯器的巨大開銷** Python 是直譯語言。在排序法的滑動窗口迴圈中,`nums[r] - nums[l]` 這樣一行簡單的程式碼,背後需要經過 Python 直譯器繁重的工作:物件類型檢查、查找、分派操作等。這個「直譯器開銷」施加在迴圈的每一步上,積少成多,成為了巨大的效能瓶頸。 ##### **2. C 語言實現的「超車道」** Python 的高效,秘訣在於其豐富的、由 C 語言實現的內建函式庫。 * **`Counter(nums)`** 這個操作,其核心的計數邏輯完全是在**高效的 C 語言層級**執行的。Python 直譯器僅僅是發起一個呼叫,然後 C 程式碼就在幕後以極高的速度完成了 O(N) 的計數工作。 * 這個方法巧妙地將最主要的計算壓力,從緩慢的 Python 迴圈轉移到了飛快的 C 語言底層。 在 Python 的世界裡,快取帶來的效益依然存在,但它已經**不足以抵銷直譯器本身的巨大開銷**。效能的瓶頸從「記憶體存取」轉變成了「直譯器速度」。因此,誰能最大限度地減少在 Python 層級的迴圈次數,誰就是贏家。 ----- ### **結論:我們學到了什麼?** 這場跨越 C++ 和 Python 的效能對決,給我們帶來了幾個深刻的啟示: 1. **Big O 是指南,而非聖經:** 它描述了演算法在規模趨於無窮大時的趨勢,但在特定規模和特定環境下,常數因子和硬體互動同樣重要。 2. **了解你的語言:** C++ 讓你更貼近硬體,記憶體模式至關重要。Python 則提供了高效的 C 語言「捷徑」,善用內建函式庫是優化的關鍵。 3. **快取意識:** 無論使用何種語言,寫出對 CPU 快取友好的程式碼,都是一個通用的優化方向。 4. **實測為王 (Profile Your Code):** 當效能成為瓶頸時,不要猜測,要用實際的效能分析工具來找出問題所在。 下一次,當你面對一個演算法選擇時,除了分析 Big O,不妨也思考一下:**我的程式碼,將在怎樣的硬體和語言環境下運行?** 這個問題,或許能引導你找到通往極致效能的真正路徑。

沒有留言: