swift - 为什么 O(n) 比 O(n^2) 花费的时间更长？

Question

我有一个 LeetCode 问题:

给定一个 M x N 矩阵，当且仅当矩阵是 Toeplitz 时返回 True。

一个矩阵是Toeplitz如果从左上角到右下角的每条对角线都具有相同的元素。

我的解决方案是(Swift):

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    if matrix.count == 1 { return true }

    for i in 0 ..< matrix.count - 1 {
        if matrix[i].dropLast() != matrix[i + 1].dropFirst() { return false }
    }

    return true
}

根据我对大 O 表示法的理解，我的算法的时间复杂度是 O(n)，而 LeetCode 最佳答案的时间复杂度是 O(n^2)。

热门答案示例:

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    for i in 0..<matrix.count-1 {
      for j in 0..<matrix[0].count-1 {
          if (matrix[i][j] != matrix[i+1][j+1]) {
              return false;
          }
      }
    }

     return true;
}

不过，我的算法需要 36 毫秒(根据 LeetCode)，而最佳答案需要 28 毫秒。

当我注释掉 if matrix.count == 1 { return true } 时，运行时间甚至更长 - 56 毫秒。

Answer 1

函数的时间复杂度也是 O(n^2)，因为函数调用 dropLast 是 O(n)。

编辑:Rup和melpomene也提到，数组的比较也将复杂度提高到O(n^2)。

此外，大 O 表示法描述了算法如何根据数据数量 n 进行缩放。为了简洁起见，它去掉了任何常量。因此，如果输入数据足够小，O(1) 的算法可能比 O(n^3) 的算法慢。