algorithm - 计算算法运行时？

Question

这更像是一个 CS 问题，但希望有人能帮助我。如果特定算法的运行时间为 T(100) = 20，我如何估算给定的 T(400) 的运行时间，a) T(n) = O(n) 或 b) T(n) = O(n^2) ？对于 a，我认为如果 100 个元素占用 20 个单位(空间或时间)，那么线性 400 个元素将占用大约 80 个单位。这种想法是否正确？如果是这样，如何处理 b) ？如果不是，计算这个的正确方法是什么？谢谢!

Answer 1

做一些假设，例如 n 足够大，您可以真正看到渐近行为，并且算法分别为 Omega(n) 和 Omega(n^2)，您可以这样进行:

a) T(n) = c * n;鉴于 T(100) = 20 我们发现 c = 0.2 和 T(400) = 80

b) T(n) = c * n^2; T(100) = 20 -> c = 0.002； T(400) = 320