当计算机速度加倍时计算 O(n)
calculating O(n) when computer speed is doubled
假设一个复杂度为 O(n) 的算法在速度为 X 的计算机上求解。
现在，同样的算法在 2X 速度的计算机上使用时可以同时解决大小为 2N 的问题。
现在如果我们在速度为 X 的计算机上有一个 O(logn) 的算法
我如何计算在2X速度的计算机上可以同时解决的问题的大小。
与 o(n^2) 类似。
这不是作业问题之类的。
只是出于好奇，正如我正在阅读的书中对上面的问题 2 所说的那样，它是 O(n^2)，但我不明白。
大O表示法不依赖于计算机速度，它只是描述算法的时间复杂度。你必须遍历数组两次的东西总是 2N，如果你把它放在一台速度是两倍的计算机上，它仍然是 2N 的时间复杂度，即使实际上它完成速度是两倍。这就是符号的美妙之处，它与处理器速度无关。
只有当您知道 运行 时间的 big-theta 并且问题足够大时，才能进行此类估计。
对于 2) 2*log(n) = log(n^2)
对于 3) 2*n^2 = (n*sqrt(2))^2
令n为当前处理的工作量，m为速度加倍时处理的工作量。请参阅此处的讨论：
https://math.stackexchange.com/questions/248306/time-complexity-why-does-doubling-the-speed-given-this-improvement
For O(log(n)):
log(m)/log(n) = 2
log(m)=2*log(n)
log(m)=log(n^2) => m=n^2
For O(n^2):
m^2/n^2 = 2 => m = sqrt(2)*n
假设一个复杂度为 O(n) 的算法在速度为 X 的计算机上求解。 现在，同样的算法在 2X 速度的计算机上使用时可以同时解决大小为 2N 的问题。
现在如果我们在速度为 X 的计算机上有一个 O(logn) 的算法 我如何计算在2X速度的计算机上可以同时解决的问题的大小。
与 o(n^2) 类似。
这不是作业问题之类的。 只是出于好奇，正如我正在阅读的书中对上面的问题 2 所说的那样，它是 O(n^2)，但我不明白。
大O表示法不依赖于计算机速度，它只是描述算法的时间复杂度。你必须遍历数组两次的东西总是 2N，如果你把它放在一台速度是两倍的计算机上，它仍然是 2N 的时间复杂度，即使实际上它完成速度是两倍。这就是符号的美妙之处，它与处理器速度无关。
只有当您知道 运行 时间的 big-theta 并且问题足够大时，才能进行此类估计。
对于 2) 2*log(n) = log(n^2)
对于 3) 2*n^2 = (n*sqrt(2))^2
令n为当前处理的工作量，m为速度加倍时处理的工作量。请参阅此处的讨论： https://math.stackexchange.com/questions/248306/time-complexity-why-does-doubling-the-speed-given-this-improvement
For O(log(n)):
log(m)/log(n) = 2
log(m)=2*log(n)
log(m)=log(n^2) => m=n^2
For O(n^2):
m^2/n^2 = 2 => m = sqrt(2)*n