O(n^2) 需要 1 秒来处理 1000 个元素。 8K需要多长时间？

Question

在图片上，抛物线 n^2 x=1000 将对应 y=1。还是必须有一些系数？是a*N^2还是(aN)^2？ 纯数学如何正确求解？

Answer 1

如果有一个二次函数 f，它描述了一个顶点位于 (0, 0) 的抛物线，则该函数始终可以写成 f: y = a * x^2 的形式，其中 a 是除零之外的任何实数，如果你想要一个非退化抛物线。从这里求解 a 系数应该非常简单 - (1000, 1) ∈ f => 1 = a * 1000^2 => a = 1e-6。因此函数 f 的方程为： y = 1e-6 * x^2。这意味着 f(8000) = 64。

更简单的方法（不计算函数）是使用规则，在处理二次函数时，自变量的 x 倍变化将导致因变量的 x^2 变化。自变量的变化为 8x => 因变量的变化为 64x => 时间为 64 秒。