演算法的逆襲：為何 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。
解決這個問題，有兩種經典的思路：
- 排序 + 滑動窗口 (Sorting + Sliding Window): 先將陣列排序，然後用兩個指針
l和r遍歷一次，找出符合條件的最長區間。時間複雜度是O(N log N)，主要瓶頸在排序。 - 雜湊表計數 (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))
#include <vector>
#include <algorithm>
#include <ranges>
class Solution {
public:
int findLHS(std::vector<int>& 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))
#include <vector>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
int findLHS(std::vector<int>& nums) {
std::unordered_map<int, int> 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))
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))
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 的效能對決，給我們帶來了幾個深刻的啟示：
- Big O 是指南，而非聖經： 它描述了演算法在規模趨於無窮大時的趨勢，但在特定規模和特定環境下，常數因子和硬體互動同樣重要。
- 了解你的語言： C++ 讓你更貼近硬體，記憶體模式至關重要。Python 則提供了高效的 C 語言「捷徑」，善用內建函式庫是優化的關鍵。
- 快取意識： 無論使用何種語言，寫出對 CPU 快取友好的程式碼，都是一個通用的優化方向。
- 實測為王 (Profile Your Code): 當效能成為瓶頸時，不要猜測，要用實際的效能分析工具來找出問題所在。
下一次，當你面對一個演算法選擇時，除了分析 Big O，不妨也思考一下：我的程式碼，將在怎樣的硬體和語言環境下運行？ 這個問題，或許能引導你找到通往極致效能的真正路徑。
