plot - 如何从情节中理解时间复杂度？

Question

我用 C 语言编写了一个程序，我在其中分配内存来存储维度为 n×n 的矩阵，然后将其提供给线性代数子例程。我在理解如何从图中识别这些操作的时间复杂度时遇到了很大的麻烦。我特别感兴趣的是确定 CPU 时间如何作为 n 的函数进行缩放，其中 n 是我的大小。

为此，我创建了一个 n = 2, 4, 8, ..., 512 的数组，并计算了这两个操作的 CPU 时间。我对每个 n 重复这个过程 10000 次，最后取平均值。因此，我想出了第二个数组，可以与我的数组 n 匹配。

有人建议我打印双对数图，我读了 here和 here也就是说，使用这种方式，“权力显示为一条直线”(2)。这是结果图(dgesv 是我使用的线性代数子程序)。

现在，我猜测我的时间复杂度是 O(log n)，因为我的两个操作都是直线(我没有考虑红线)。我看到了线性复杂度、对数复杂度等之间的形状差异。但我仍然怀疑我是否应该说说 dgesv 的时间复杂度，例如。我敢肯定有一种方法我根本不知道，所以如果有人能帮助我理解如何正确地看待这个情节，我会很高兴。

PS:如果有一个特定的社区可以发布这个问题，请告诉我，这样我就可以移动它，避免这里出现更多困惑。谢谢大家。

Answer 1

看你的黄线，它似乎是从 (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可能 has a cost 2/3 n^3(虽然 O(n^2.5) 是 theoretically possible )。