一個簡單的迴圈

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

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)