0 
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 但我很确定这实际上是错误的。谁能解释这段代码的时间复杂度是多少？

4

2 回答 2

0 
 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)

我被教导的方式是，对于每个循环，它都是 O(n)，因此，嵌套循环自然是 O(n^2)，并且每个条件或操作n + n ..nth都是 O(n^2 + n) = O(n^2)

希望能有所帮助。

查看下面的资源以获得更深入的解释。

资源：

于 2020-04-28T16:52:56.263 回答
0

每个迭代 (tiles.length*tiles.length) 次有 2 个 for 循环。所以它是：

比较次数：

  • 第一组比较（i=0）：tiles.length 2

  • 第二组比较（i=1）：tiles.length 2 -1

  • .

  • .

  • 最后一组比较（i=tiles.length 2 -1）：1

= ( ( tiles.length 2 ) + ( tiles.length 2 -1 ) + ( tiles.length 2 - 2) .... + 2 + 1 )

= O(tiles.length 3 )

于 2020-04-28T16:45:28.587 回答