Временная сложность этого вложенного цикла

Question

for (int i = 0; i < this.tiles.length * this.tiles.length; i++) {
        int row = i / this.tiles.length;
        int col = i % this.tiles.length;
        for (int j = i+1; j < this.tiles.length * this.tiles.length; j++) {
            int compareRow = j / this.tiles.length;
            int compareCol = j % this.tiles.length;
            if(this.tiles[compareRow][compareCol] < this.tiles[row][col]) {
                count++;
            }
        }
    }

Мне нужно вычислить временную сложность этой функции, я сначала подумал, что это ~ n * n-1, но я почти уверен, что это на самом деле неправильно. Кто-нибудь может объяснить, какова временная сложность этого куска кода?

Answer 1

 for (int i = 0; i < this.tiles.length * this.tiles.length; i++) { //O(n)
        int row = i / this.tiles.length; 
        int col = i % this.tiles.length; 
        for (int j = i+1; j < this.tiles.length * this.tiles.length; j++) { //O(n^2) it's squared because there are two loops
            int compareRow = j / this.tiles.length; //n +
            int compareCol = j % this.tiles.length; //+ n
            if(this.tiles[compareRow][compareCol] < this.tiles[row][col]) {  //n
                count++; 
            }
        }
    }

O (n ^ 2 + n) == O (n ^ 2)

Способ, которым меня учили, состоял в том, что для каждого l oop это O ( n) так, вложенный l oop будет, естественно, O (n ^ 2), а с каждым условием или операцией будет n + n ..nth, где O (n ^ 2 + n) = O (n ^ 2)

Надеюсь, что это немного помогло.

Изучите ресурс ниже для более подробного объяснения.

Ресурсы:

• https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Answer 2

Есть 2 цикла for для каждой итерации (tile.length * tile.length) раз. Так оно и есть:

Количество раз сравнения:

• Первый набор сравнения (i = 0): tile.length ²

• Второй набор сравнения (i = 1): плитка. Длина ² -1

• .

• .

• Последний набор сравнения (i = tile.length ² -1): 1

= ((плитка. Длина ² ) + (плитка. Длина ² -1) + (плитка. Длина ² - 2) .. ..... + 2 + 1)

= O (длина плитки ³ )