4 个嵌套 'for' 循环的最佳和最坏情况时间复杂度？

Question

嵌套 for 循环的最差和最佳时间复杂度是多少？

int compare(int n, int A[][]) {
    int i, j, k, m;
    for (i=1; i<=n; i++) {
        for (j=1; j<=n; j++) {
            for (k=1; k<=n; k++) {
                for (m=1; m<=n; m++) {
                    if (A[i][j] == A[k][m] && !(i==k && j==m))
                        return 1;
                }
            }
        }
    }
return 0;
}

我试图自己解决它，但对最内层循环如何增加复杂性感到非常困惑。

Answer 1

最佳情况时间复杂度是常数，O(1)。当网格的第一个和第二个元素 A 相等时，将发生最佳情况。

    1 1 x x x
A = x x x x x
    x x x x x
    x x x x x

最坏情况下的复杂度是O(n^4)。当网格的所有元素 A 都是唯一的时，将发生最坏的情况。

    1  2  3  4
A = 5  6  7  8
    9  10 11 12
    13 14 15 16

Answer 2

最佳情况：O(1)，当 A[1][1] = A[1][2]

最坏情况：O(n⁴)，当没有重复元素时 -> 你最终会为它的每个元素迭代整个数组。

请注意，您可以使用映射或集合（将其称为结构）更有效地实现它：

迭代数组
如果结构已经有A[i][j],return1
将A[i][j]添加到结构中
return数组迭代结束后0

这会给你一个更糟糕的情况 O(n² log n) 或 O(n²)，具体取决于您使用的结构

4 个嵌套 'for' 循环的最佳和最坏情况时间复杂度？

Best and the worst case time complexity for 4 nested 'for' loops?

c

algorithm

for-loop

time-complexity

nested-loops