如何从情节中理解时间复杂度？
how to understand time complexity from a plot?
我用 C 编写了一个程序，我在其中分配内存来存储尺寸为 n×n 的矩阵，然后将其馈入线性代数子例程。我在理解如何从图中识别这些操作的时间复杂度时遇到了很大的麻烦。特别是，我有兴趣确定 CPU 时间尺度如何作为 n 的函数，其中 n 是我的尺寸。
为此，我创建了一个 n = 2, 4, 8, ..., 512 的数组，并计算了两个操作的 CPU 时间。我对每个 n 重复这个过程 10000 次，最终我取了平均值。因此，我想出了第二个数组，可以与我的 n.
数组匹配
有人建议我打印双对数图，我阅读了 here and here that, using this way, "powers shows up as a straight line" (2)。这是结果图（dgesv 是我使用的线性代数子程序）。
现在，我猜我的时间复杂度是 O(log n) 因为我的两个操作都是直线（我 不是 考虑红线）。我看到了线性复杂度、对数复杂度等之间的形状差异。但我仍然怀疑我是否应该说说 dgesv 的时间复杂度。我敢肯定有一种方法我根本不知道，所以如果有人能帮助我理解如何正确地看待这个情节我会很高兴。
PS：如果有特定的社区post 这个问题，请告诉我，这样我就可以移动它，避免这里出现更多混乱。谢谢大家
看你的黄线，它似乎是从 (0.9, -2.6) 到 (2.7, 1.6)，斜率大约等于 2.5。当您绘制 log(t) 与 log(n) 时，这意味着：
log(t) = 2.5 log(n) + c
或者，对双方取幂：
t = exp(2.5 log(n) + c) = c' n^2.5
2.5 的威力可能被低估了dsegv likely has a cost of 2/3 n^3 (though O(n^2.5) is theoretically possible)。
我用 C 编写了一个程序，我在其中分配内存来存储尺寸为 n×n 的矩阵，然后将其馈入线性代数子例程。我在理解如何从图中识别这些操作的时间复杂度时遇到了很大的麻烦。特别是，我有兴趣确定 CPU 时间尺度如何作为 n 的函数，其中 n 是我的尺寸。
为此，我创建了一个 n = 2, 4, 8, ..., 512 的数组，并计算了两个操作的 CPU 时间。我对每个 n 重复这个过程 10000 次，最终我取了平均值。因此，我想出了第二个数组，可以与我的 n.
数组匹配有人建议我打印双对数图，我阅读了 here and here that, using this way, "powers shows up as a straight line" (2)。这是结果图（dgesv 是我使用的线性代数子程序）。
现在，我猜我的时间复杂度是 O(log n) 因为我的两个操作都是直线（我 不是 考虑红线）。我看到了线性复杂度、对数复杂度等之间的形状差异。但我仍然怀疑我是否应该说说 dgesv 的时间复杂度。我敢肯定有一种方法我根本不知道，所以如果有人能帮助我理解如何正确地看待这个情节我会很高兴。
PS：如果有特定的社区post 这个问题，请告诉我，这样我就可以移动它，避免这里出现更多混乱。谢谢大家
看你的黄线，它似乎是从 (0.9, -2.6) 到 (2.7, 1.6)，斜率大约等于 2.5。当您绘制 log(t) 与 log(n) 时，这意味着：
log(t) = 2.5 log(n) + c
或者，对双方取幂：
t = exp(2.5 log(n) + c) = c' n^2.5
2.5 的威力可能被低估了dsegv likely has a cost of 2/3 n^3 (though O(n^2.5) is theoretically possible)。