algorithm - 计算转置矩阵的时间复杂度

Question

该代码是一段尝试转置矩阵的代码的摘要版本。我的任务是找出这个程序的时间复杂度。

我只对发生交换次数的时间复杂度感兴趣。我发现在交换的外循环上它发生了 n-1 次，而对于内循环它发生了 (n^2 -n)/2 次。

---

我通过用数字代替 n 推导出这些解决方案。

• 当n=4时，我的内层循环会循环1+2+3次
• 当 n=5 时，我的内部循环会循环 1+2+3+4 次
• 因此 innerloop=(n^2 - n)/2

我如何计算这段代码的时间复杂度？

---

我在网上看到有人只是从他的内循环计数中获取值并确定它是一个 O(n) 复杂度。

---

[编辑]我是否也需要在其他循环中迎合计算时间复杂度？

Answer 1

您的交换算法是一个明确的(1+2+3+...n) 案例，translates to n×(n+1)/2.

由于计算中的常量和低阶部分不计入大 O 表示法，因此这转换为 O(n^2)。

采用其他循环不会改变您的时间复杂度，因为它们也是 O(n^2)。就大 O 而言，编写 O(3(n^2)) 是没有意义的，因为常量被丢弃了。

但是在这里可以帮助您的是您不需要为更复杂的 swap for 循环操心。 (我不是说你在学习的时候。我是说，当你处理现实世界的问题时。)

附带说明，我建议阅读破解编码面试(第 6 版)(2015 年)Big O 部分的示例 3 strong> by - McDowell, Gayle，它解决了这个确切的情况和许多类似的情况。