Наилучшая и наихудшая временная сложность для 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] = A [1] [2]

Наихудший случай: O (n ⁴ ), когда естьне повторяющийся элемент -> вы заканчиваете итерацией всего массива для каждого его элемента.

Обратите внимание, что вы могли бы реализовать его более эффективно с помощью карты или набора (назовем его структурой):

• Перебор массива
• Если в структуре уже есть A [i] [j], вернуть 1
• Добавить A [i] [j] в структуру
• вернуть 0 после окончания итерации массива

Это даст вам худший случай O (n ² log n) или O (n ² ),в зависимости от используемой вами структуры

Answer 2

Наилучшая сложность по времени постоянна, 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