嵌套循环

以下函数通过获取每个元素来检查数组是否有任何重复，然后遍历整个数组以查看该元素是否存在

_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。