如何从图表中理解时间复杂度？

Question

如何从图表中理解时间复杂度？

3

我用C语言编写了一个程序，其中我分配内存来存储一个大小为n×n的矩阵，然后将其提供给线性代数子例程。我很难理解如何从图表中确定这些操作的时间复杂度。特别是，我想确定CPU时间如何随着n的增加而变化，其中n是我的大小。

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

有人建议我使用双对数图表打印，并且我在这里和这里阅读到，使用这种方式，"幂函数显示为一条直线"（2）。这是生成的图表（dgesv是我使用的线性代数子程序）。

现在，我猜测我的时间复杂度为O(log n)，因为我对两个操作都得到了直线（我没有考虑红线）。我看到了不同形状的区别，比如线性复杂度、对数复杂度等等。但我仍然对dgesv的时间复杂度是否应该有所表示存在疑虑。我确定有一种我完全不知道的方法，所以如果有人能帮助我“理解如何正确地查看此图”，我会很高兴的。

PS：如果有一个特定的社区可以发布这个问题，请让我知道，这样我就可以避免更多的混乱。谢谢大家。

- Mattia Paterna

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wrwrwr · Accepted Answer

拿出你的黄色线，它似乎从（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成本，因为它很可能具有2/3 n^3的代价（尽管O(n^2.5)在理论上是可能的）。请保留HTML标签。