巢狀迴圈

以下函式通過獲取每個元素來檢查陣列是否有任何重複，然後遍歷整個陣列以檢視該元素是否存在

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

內迴圈在每次迭代時執行許多與 n 一致的操作。外迴圈也執行一些常量操作，並執行內迴圈 n 次。外環本身執行 3 次。因此內迴圈內的操作執行 4 次，外迴圈中的操作執行 5 次，並且對 i 的賦值執行一次。因此，複雜性將類似於 an^2 + bn + c，並且由於最高項是 n^2，因此 O 符號是 O(n^2)。

你可能已經注意到，我們可以通過避免多次進行相同的比較來改進演算法。我們可以從內環中的 i + 1 開始，因為它之前的所有元素都已經針對所有陣列元素進行了檢查，包括索引 i + 1 中的元素。這允許我們放棄 i == j 支票。

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

顯然，第二個版本操作較少，因此效率更高。這如何轉化為 Big-O 表示法？那麼，現在內環體執行了 13 次。這仍然是二度多項式，所以仍然只是 O(n^2)。我們已經明顯降低了複雜性，因為我們將操作的數量大致除以 2，但我們仍然處於 Big-O 定義的相同複雜性類別中。為了將複雜性降低到較低的等級，我們需要將操作次數除以與趨勢無限的東西 15。