时间戳

首页 > 解决方案 > 当计算机速度加倍时计算 O(n)

algorithm - 当计算机速度加倍时计算 O(n)

问题描述

  1. 假设在速度为 X 的计算机上解决了 O(n) 的算法。现在，当在速度为 2X 的计算机上使用相同的算法时，可以同时解决大小为 2N 的问题。

  2. 现在，如果我们在速度为 X 的计算机上有一个 O(logn) 的算法，我如何计算可以在 2X 速度的计算机上同时解决的问题的大小。

  3. 对于 o(n^2) 也是如此。

这不是任何作业问题等。只是好奇，正如我正在阅读的书对上面的问题 2 所说，它是 O(n^2)，我不明白。

标签： algorithmtime-complexity

解决方案

只有当您知道运行时间的大θ，并且只有在问题规模足够大的情况下，这种估计才有可能。

对于 2)2*log(n) = log(n^2)

对于 3)2*n^2 = (n*sqrt(2))^2

推荐阅读