algorithm - 我们如何使用渐近复杂度计算算法的运行时间？

Question

如果给定某个算法的复杂度，计算N^3的运行时间的程序是什么。

Answer 1

有两种方法可以解决这个问题:

1. 增量

我们需要从 n=50 重新计算到 n=300，这是 n 的 6 倍。给定复杂度 θ(n³) 6 倍将导致运行时间延长 216 (6³) 倍。对于 n=300，这给了我们 t=2160s

1. 绝对

运行时间是某个未知常数 x 乘以复杂度 n³。找出 x 我们解决这个方程:t=x*n³ 或者更确切地说 10=x*125000 这将给我们 x=1/的最终结果12500 现在我们需要为新的 n t=(1/12500)*300³ 找到新的时间，它简化为 t=60*12*3，这给了我们相同的结果2160 秒。