HackerRank对角线差异的时间复杂度

Question

谁能帮我确定以下代码的时间复杂度吗？

背景：这是HackerRank algorithm problem，其中编辑部分列出了时间复杂度为O（n ^ 2）的解决方案，但我认为它的O（n）。

我相信它的O（n），因为我们只使用一个循环遍历二维数组，而不使用嵌套循环，而只循环遍历该数组一次。

我是正确的还是缺少什​​么？

解决方案>>

//arr is a 2 dimensional array containing an equal number of rows and columns
function diagonalDifference(arr) {
  let diff = 0;
  const length = arr.length - 1;
  for (let i = 0; i < arr.length; i++) {
    diff += arr[i][i] - arr[i][length - i];
  }
  return Math.abs(diff);
}
问题

给出一个正方形矩阵（AKA 2D数组），计算其对角线之和之间的绝对差。

例如，方阵arr

如下所示：

1 2 34 5 69 8 9

从左到右对角线= 1 + 5 + 9 =15。从右到左对角线= 3 + 5 + 9 =17。它们的绝对差是| 15-17 |。 = 2。

有人可以帮助我确定以下代码的时间复杂度吗？背景：这是一个HackerRank算法问题，其中编辑部分列出了时间复杂度为O（n ^ ...

Answer 1

代码的时间复杂度为O(n)，其中矩阵的长度。正确地说，循环仅运行一次，并且也等于行/列的数量，即矩阵的长度。没有嵌套循环。因此，时间复杂度肯定是，对于所有情况，最好（最坏）平均为O（n）。