从 运行 时间和变化率估计算法的增长顺序

Question

我是练习算法的初学者。下面的列表代表了一个算法 I 运行 并记录了变化的次数和比例。我不确定如何从这个列表中找出增长顺序。我必须考虑哪些因素？我非常感谢一个解释性的答案。

 N  |seconds | ratio | log(base of 2) ratio
---------------------------------------
512   0.12    4.14      2.05
1024  0.49    4.24      2.08
2048  2.08    4.24      2.08
4096  8.83    4.24      2.08

Answer 1

比较最小输入与各种较大输入的时间：

• N (512->1024) 增加 2 倍会导致 运行 时间增加 4 倍。
• N (512->2048) 增加 4 倍导致 运行 时间增加 16 倍。
• N (512->4096) 增加 8 倍导致 运行 时间增加 64 倍。

据此，您可以推断 N 增加 kx 将导致 k²x 在 运行 时间内增加，表示 O(n²) 算法。