1

如果有 2 个时间复杂度为 O(2/n) 和 O(100) 的函数。哪个函数的执行时间更短？是否有任何时间复杂度为 2/n 的实函数？（在一些算法问题论文中找到了这个）

4

4 回答 4

2

首先，在 O 表示法（以及 Theta 和 Omega）中，您可以忽略任何常数，因为定义已经包含“for some constant k ”部分。

所以，基本上，O(100) 等价于 O(1)，而 O(2/n) 等价于 O(1/n)。哪个执行时间更快 - 取决于n。如果我假设100和2/n直接用于计算执行时间，那么执行时间是：

  • 在所有情况下， O(100)为100（时间单位）
  • 超过100（时间单位）对于O(2/n)对于n < 0.02
  • 小于100（时间单位）对于O(2/n)对于n >= 0.02

现在，我希望这个问题纯粹是理论上的，因为实际上没有 O(1/n) 复杂度的算法——这意味着它需要更少的时间（这是每数据量的记录时间，这只是时间）它需要处理的数据更多。我希望这很清楚，没有任何算法可以花费0时间来处理无限量的数据。

另一个复杂度 O(100) 是一种算法，无论输入数据是什么，都采用相同的步骤，因此始终具有恒定的执行时间（实际上，它只需要以一个常数为界，它可以运行得更快有时）。例如，一个程序从整数文件中读取输入，然后返回该文件中前 100 个数字的总和，如果不存在 100 个数字，则返回所有数字的总和。由于它总是最多读取 100 个数字（其余的可以忽略）并将它们相加，因此它受到固定步数的限制。

于 2012-10-08T08:50:40.777 回答
1

当然，这取决于 N 的值。O(100) 基本上是固定时间，并且可能比 O(2/N) 运行得更快或更慢，具体取决于 n 是多少。

我想不出一个 O(2/N) 算法，随着更多的数据变得更快……听起来有点奇怪。

于 2012-10-08T08:40:37.467 回答
1

做任何事情的O(2/n)算法实际上是不可能的。

算法是产生结果的有限步骤序列。由于计算机上的“步骤”需要一定的时间（例如至少一个 CPU 周期），因此算法获得O(2/n)时间的唯一方法是，如果它需要零时间来达到足够大的n. 因此它什么也不做。

撇开算法和时间复杂度不谈：一个O(2/n)函数是“小于”常数，从某种意义上说，一个O(2/n)函数必然趋向于 0，而 n 趋于无穷大，而一个O(1)函数并不一定会那样做。

对本文问题文本的注释：任何O(100)也是 的O(1)函数，以及任何O(2/n)也是 的函数O(1/n)。在其中编写带有不必要常量的 big-O 并没有多大意义，但由于它是一项检查，所以它可能会让您感到困惑。

于 2012-10-08T08:44:55.380 回答
1

我不熟悉任何具有O(2/n)运行时间的算法，我怀疑是否存在，但让我们看看数学问题。

数学问题应该是： (1) 是1O(2/n)的子集(2) 是的子集吗？O(1)O(1)O(2/n)

  1. 是的。让f(n)成为一个函数O(2/n)- 这意味着有常数 c,N 使得对于每个n > N: c*f(n) < 2/n。也有常数c2,N2，例如c*2/n < 1对于 each n > N2，因此min{c1,c2} * f(n) < 1对于 each n > max{N1,N2}。O(2/n)的子集也是O(1)

  2. 不。因为lim(2/n) = 0在无穷大处，对于每个c,N，都有n>N这样的，2/n < 1*c因此f(n) = 2/n不在 中O(1)，而在O(2/n)

结论： 一个功能O(2/n)也是O(1)- 但不是相反。
这意味着 - 每个函数的O(2/n)比例“小于”然后 1。

(1) 与 相同O(100)，因为O(1) = O(100)

于 2012-10-08T08:49:58.927 回答