时间复杂度与CPU速度k倍的关系
Relationship between time complexity and CPU speed k-fold
如果我们将处理器的速度提高 10 倍，问题的大小会发生什么变化？
- 在线性情况下，对于时间复杂度为
n 的算法 A 和
尺寸s_1，允许尺寸变为10s_1.
- 在二次情况下，那么对于时间复杂度
n^2，大小s_2的算法B，允许大小变为\sqrt{10}s_2 = 3.16s_2.
- 等等
对于第二种情况，如果第二种算法的复杂度为n^2，大小为s_2，那么如果我们将CPU速度提高10倍，我们将处理数据快 10 倍，因此如果我们最初处理 T 大小的数据，现在我们将在 T/10 时间内处理相同大小 s_2 的数据，这是 1/10 的时间，以防我们CPU 速度提高了 10 倍。现在，我们如何将其与答案联系起来 3.16xs_2?
问题：如果我们将 CPU 速度提高 10 倍，您能否说明算法 B 的大小增加到 \sqrt{10}s_2 = 3.16s_2 的情况？
让我们使用新的表示法使其更容易理解。
首先，如果时间复杂度为n^2，大小为x，我们可以概括地说完成处理所需的时间为x^2，只需代入[=13] =] 对于 x。让我们调用旧尺寸 x 和新的允许尺寸 y.
这里我假设“允许大小”的意思是“可以在与以前相同的时间内处理的新的最大大小是多少”。所以我们可以为时间（t）设置一个等式：
x^2 = t 使用旧处理器
现在有了速度十倍的新处理器，我们知道在完美世界中处理该大小的时间会少十倍：
x^2 = t/10
隔离时间我们得到
10 * x^2 = t
现在我们想要花费相同时间的新尺寸：
y^2 = t
所以根据最后两个等式，我们知道两边相等，因为它们同时相等：
10 * x^2 = y^2
现在我们只需要解决y，我们可以用与以前相同的时间处理的新尺寸。
\sqrt{10x^2} = y
\sqrt{10} * x = y
3.16 * x = y
所以现在我们知道，使用相同处理时间的新“允许大小”y 是旧大小 x: 3.16s_2 的 3.16 倍，用你的符号表示。
如果我们将处理器的速度提高 10 倍，问题的大小会发生什么变化？
- 在线性情况下，对于时间复杂度为
n的算法 A 和 尺寸s_1，允许尺寸变为10s_1. - 在二次情况下，那么对于时间复杂度
n^2，大小s_2的算法B，允许大小变为\sqrt{10}s_2 = 3.16s_2. - 等等
对于第二种情况，如果第二种算法的复杂度为n^2，大小为s_2，那么如果我们将CPU速度提高10倍，我们将处理数据快 10 倍，因此如果我们最初处理 T 大小的数据，现在我们将在 T/10 时间内处理相同大小 s_2 的数据，这是 1/10 的时间，以防我们CPU 速度提高了 10 倍。现在，我们如何将其与答案联系起来 3.16xs_2?
问题：如果我们将 CPU 速度提高 10 倍，您能否说明算法 B 的大小增加到 \sqrt{10}s_2 = 3.16s_2 的情况？
让我们使用新的表示法使其更容易理解。
首先，如果时间复杂度为n^2，大小为x，我们可以概括地说完成处理所需的时间为x^2，只需代入[=13] =] 对于 x。让我们调用旧尺寸 x 和新的允许尺寸 y.
这里我假设“允许大小”的意思是“可以在与以前相同的时间内处理的新的最大大小是多少”。所以我们可以为时间（t）设置一个等式：
x^2 = t 使用旧处理器
现在有了速度十倍的新处理器，我们知道在完美世界中处理该大小的时间会少十倍：
x^2 = t/10
隔离时间我们得到
10 * x^2 = t
现在我们想要花费相同时间的新尺寸：
y^2 = t
所以根据最后两个等式，我们知道两边相等，因为它们同时相等：
10 * x^2 = y^2
现在我们只需要解决y，我们可以用与以前相同的时间处理的新尺寸。
\sqrt{10x^2} = y
\sqrt{10} * x = y
3.16 * x = y
所以现在我们知道，使用相同处理时间的新“允许大小”y 是旧大小 x: 3.16s_2 的 3.16 倍，用你的符号表示。