求解自定义对角线差算法的精确时间复杂度

你的代码时间复杂度判定：O(n²) #

你的代码本质上是完整遍历了整个n×n的矩阵：

• 外层逻辑中，i从0到n-1（共n次循环），每次i固定时，j会从0遍历到n-1（共n次循环）
• 整个循环体总共执行了n×n次，每次循环内的判断、加法操作都是O(1)的常数时间操作
• 因此整体时间复杂度是O(n²)，和直接遍历所有元素的常规解法复杂度完全一致，并没有达到你想要的优化效果

为什么会误以为是O(n)？ #

你可能混淆了「对角线元素的数量」和「代码实际遍历的元素数量」：对角线确实只有最多2n个元素（n为奇数时中间元素会重复），但你的代码并没有直接定位到这些元素，而是遍历了矩阵的每一个元素，再通过条件判断筛选出对角线元素，因此并没有减少遍历的总次数。

真正的O(n)优化实现 #

要达到O(n)复杂度，不需要遍历整个矩阵，直接定位对角线元素即可：

function diagonalDifference(arr = [[]]) {
  const n = arr.length;
  let mainSum = 0;
  let secondarySum = 0;
  
  for (let i = 0; i < n; i++) {
    mainSum += arr[i][i];
    secondarySum += arr[i][n - 1 - i];
  }
  
  return Math.abs(mainSum - secondarySum);
}

这个版本只循环n次，每次直接访问主对角线(i,i)和副对角线(i, n-1-i)的元素，总操作次数是O(n)，完全符合你的优化需求。

内容的提问来源于stack exchange，提问作者Mário Alfredo Jorge