爲什麼需要時間複雜度？¶

想象一下，你有一個任務：在一本電話號碼簿裏找一個特定的名字。有兩種方法：

• 方法一：從頭開始，一頁一頁翻，直到找到目標名字。如果名字在最後一頁，你需要翻很多頁。
• 方法二：直接用目錄索引，輸入名字快速定位。

顯然，方法二更快，尤其是電話簿很大的時候。這就是我們常說的“效率”問題——不同算法的“快慢”差異。

在編程中，我們寫的每個算法（比如查找、排序）都有執行時間。但直接計算“需要多少秒”不現實（因爲電腦性能、編譯器不同，結果會變）。所以我們用時間複雜度來抽象描述算法的“效率趨勢”。

時間複雜度O(n)是什麼？¶

時間複雜度是衡量算法執行時間隨輸入數據規模增長的趨勢。它用大O符號（比如O(n)）表示，核心是看“當輸入規模n變大時，算法需要的操作次數如何增長”。

• O(n) 表示“線性時間複雜度”。這裏的 n 通常指輸入數據的規模（比如數組長度、元素個數）。
• 線性關係：當輸入規模n增大時，算法需要的操作次數與n成正比。舉個例子：
• 如果n=5（5個元素），算法需要5次操作；
• 如果n=10，算法需要10次操作；
• 如果n=1000，算法需要1000次操作。

用例子理解O(n)¶

例子1：遍歷數組找目標元素¶

假設你要在一個數組中找“目標數字”，最簡單的方法是逐個檢查每個元素：

def find_target(arr, target):
    for num in arr:  # 循環n次（n是數組長度）
        if num == target:
            return True
    return False

• 操作次數：最壞情況下，要檢查整個數組的所有元素（比如目標不存在，或在最後一個位置）。假設數組有n個元素，就需要n次比較操作。
• 時間複雜度：O(n)，因爲操作次數與n成正比（n越大，操作次數線性增加）。

例子2：打印所有元素¶

另一個例子：打印數組中的所有元素：

def print_all(arr):
    for num in arr:  # 循環n次
        print(num)

• 操作次數：同樣，需要n次打印操作（每個元素打印一次）。
• 時間複雜度：O(n)。

爲什麼用大O表示法？¶

如果直接說“這個算法需要n次操作”，可能會讓人誤解爲“n=1000時要1000次”，但實際上，n=1000和n=10000時，操作次數會從1000變成10000——這就是“線性增長”的含義。

大O表示法的核心是忽略常數和低階項，只關注“輸入規模n增長時，操作次數的增長趨勢”。例如：
- O(n) 表示“操作次數 ≈ n”；
- O(2n+5) 其實也等於O(n)（因爲2和5是常數，n增長時，它們的影響可以忽略）；
- O(n+1000) 也等同於O(n)。

O(n)和其他複雜度的對比¶

我們常見的時間複雜度有以下幾種（按效率從高到低）：

可以看出：O(n)比O(n²)更高效，但不如O(1)或O(log n)高效。

關鍵總結¶

• O(n) 是線性時間複雜度，表示算法執行時間與輸入規模n成正比；
• n 通常指輸入數據的規模（如數組長度、列表元素個數）；
• 大O表示法 只關注“趨勢”，不關心具體時間或常數；
• 爲什麼重要：理解O(n)是數據結構和算法的基礎，能幫你寫出更高效的代碼，避免“暴力解法”導致的超時問題。

下次遇到算法問題時，不妨先想想“這個算法的時間複雜度是多少？”，尤其是當數據規模很大時，O(n)和O(n²)的差距會非常明顯！