这个算法的具体时间复杂度是多少？

Question

我尝试在此 HackerRank 链接（https://www.hackerrank.com/challenges/diagonal-difference/problem?isFullScreen=true）解决问题，但我想避免实现 ( O(n^2 ） ） 算法。相反，我设计了下面的版本。然而，我对它的复杂性很好奇；它看起来是 ( O(n) )，但由于最终条件仅当

i

遍历列时

j

才会递增，因此它实际上可能更接近 ( O(n^2) )。有人可以帮我理解这一点吗？

function diagonalDifference(arr = [[]]) {
  let i = 0;
  let j = 0;
  let mainDiagonal = 0;
  let secondDiagonal = 0;

  const rows = arr[0].length;

  while (i < rows) {
    if (i === j) {
      mainDiagonal += arr[i][j];
    }

    if (j + i === rows - 1) {
      secondDiagonal += arr[i][j];
    }

    if (j === rows - 1) {
      j = 0;
      i++;
    } else {
      j++;
    }
  }

  return Math.abs(mainDiagonal - secondDiagonal);
}

我问了 ChatGPT，它指出复杂度为 ( O(n) )，而 Codeium 建议为 ( O(n^2) )。

Answer 1

复杂度是

O(n^2)

。

该代码虽然只有一个外循环，但编写的条件使得每个矩阵单元都有一个运算。您基本上是在对每一行的每一列进行交互。因此，如果有 6 行和 6 列，则将执行 36 次操作。因此O(n^2)。