为何O(n)时间复杂度的托普利茨矩阵Swift算法比O(n²)解法耗时更长？

我在LeetCode上遇到了托普利茨矩阵的问题，题目要求是：给定M×N矩阵，当且仅当该矩阵为托普利茨矩阵时返回True（托普利茨矩阵定义为所有左上到右下的对角线元素均相同）。

我自己实现了一个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(n)，但在LeetCode上运行耗时36ms；而另一个时间复杂度看似是O(n²)的最优解法示例：

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; 
}

却仅耗时28ms。更奇怪的是，当我注释掉if matrix.count == 1 { return true }这行代码后，我的解法耗时甚至增至56ms，这到底是为什么呢？

拆解耗时差异的原因 #

其实这里的核心不是理论时间复杂度的差距，而是Swift标准库方法的底层开销和LeetCode测试用例的实际分布，还有CPU分支预测的影响：

1. dropLast()/dropFirst()的隐式额外开销
   你的解法里用数组切片比较的方式，看起来代码简洁，但dropLast()和dropFirst()会创建新的数组切片对象，而切片的相等性判断本质上还是要遍历所有元素逐一对比——这和双层循环的遍历次数其实是一样的，都是O(M*N)的时间复杂度。但切片的创建、内存分配，以及Swift中数组切片比较的底层逻辑，会带来额外的常数时间开销；而双层循环直接通过下标访问元素，没有这些中间对象的创建步骤，执行效率自然更高。

2. “提前优化”反而拖慢了速度
   你加的if matrix.count == 1判断，本意是提前返回优化，但如果LeetCode的测试用例里单行矩阵的占比极低，CPU的分支预测器会频繁猜错这个分支的走向（因为大部分情况都不会走这个分支），反而会因为分支预测失败带来额外的性能损耗。当你注释掉这行后，虽然少了一个分支，但你的解法本身的切片开销被完全暴露，加上如果测试用例里有不少大矩阵，就会导致耗时进一步上升。

3. 理论时间复杂度的误区
   你觉得自己的解法是O(n)，但实际上它和双层循环的时间复杂度是等价的——两者都需要遍历所有需要验证的对角线元素，总次数都是(行数-1)*(列数)，本质都是O(M*N)。只是你的解法用了更“高级”的标准库方法，但并没有减少实际的遍历工作量，反而多了额外的中间步骤。

总结来说：在性能敏感的场景下，直接的下标访问往往比标准库的便捷方法更高效；而看似合理的“提前优化”，如果不符合测试用例的实际分布，反而会因为分支预测的问题拖慢整体性能。

内容的提问来源于stack exchange，提问作者user9847926