一個簡單的迴圈

以下函式查詢陣列中的最大元素：

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

輸入大小是陣列的大小，我在程式碼中稱為 len。

讓我們統計一下操作。

int max = INT_MIN;
size_t i = 0;

這兩個任務只進行一次，因此這是兩次操作。迴圈的操作是：

if (max < array[i])
i++;
max = array[i]

由於迴圈中有 3 個操作，並且迴圈完成了 n 次，我們將 3n 新增到我們現有的 2 個操作中以獲得 3n + 2。所以我們的函式需要 3n + 2 操作才能找到最大值（其複雜度為 3n + 2）。這是一個多項式，其中增長最快的項是 n 的因子，因此它是 O(n)。

你可能已經注意到操作的定義不是很明確。例如，我說 if (max < array[i]) 是一個操作，但根據架構，這個語句可以編譯為例如三個指令：一個記憶體讀取，一個比較和一個分支。我還認為所有操作都是相同的，即使例如記憶體操作比其他操作慢，並且它們的效能會因例如快取效果而變化很大。我也完全忽略了 return 語句，即為函式建立一個框架的事實等。最後它與複雜性分析無關，因為無論我選擇計算操作的方式如何，它只會改變係數 n 因子和常數，因此結果仍然是 O(n)。