algorithm - 更快计算机上的复杂度等级

Question

如果算法的复杂度为 O(LogN)，并在旧机器上用 1 秒解决了 N = 10^6 的问题。我怎样才能在新机器上以两倍的速度同时计算 N 可解？

我想也许我可以计算出常数 1/log10^6 然后用它来得到其余的但我认为这是不对的。谁能指导我解决这个问题的步骤？

谢谢

Answer 1

旧机器:在时间 T 内，我们有 O(log N) 个 cpu 周期。

新机器快 2 倍，所以我们在同一时间 T 内有 0(2 log N) 个 cpu 周期。

O(2 log N) = 0 (log N^2)

因此我们可以同时有效地处理 N^2 个数据。