主页 / 问题 / 707355
Accepted
Artur Panteleev
Asked:2020-08-18 03:44:13 +0000 UTC2020-08-18 03:44:13 +0000 UTC

是否存在具有 O(1/n) 复杂度的真实算法？

  • 772

是否存在具有 O(1/n) 复杂度的真实算法？我脑子里只有这样的废话：

function test(n) {
  for (i=1; i<100000/n; i++) {
    dosomething();
  }
}
алгоритм

3 个回答

  1. Best Answer

    它们甚至在理论上都不存在。因为这是一个上限。

    O(C + 1/n) = O(C) = O(1)

    其中C是除 0 以外的某个常数。

    它不能等于 0，因为在任何情况下，我们至少有开销来获取n本身和使用它。

    因为如果我们根本不使用n，那么复杂度显然不依赖于它并且不可能是O(1/n)。如果我们使用它，那么我们将至少引用它一次，并且常数将非零。

    替代理由：假设有这样一个算法，但是如果n加倍，它的执行时间减半，如果n足够大，它应该变得少于一条处理器指令，这是不可能的。

    即使在问题的代码中

    for (i=1; i<100000/n; i++) {

    当n超过 100000 时会发生什么？

    我们将有 4 个操作：赋值、除法、比较和退出函数。这是 O(1) - 它不再能够随着n 的增长而减少。

    • 39

  2. 不，它不存在。

    首先，让我们记住什么是渐近线：

    让我们有一些曲线 y = A(x)。那么渐近线 y = B(x) 就是这样一条曲线，当 A 沿 x 轴移动到无穷远时，A 可以说是“按压”到该曲线。

    从图形上看，它看起来像这样：

    来源：https ://en.wikipedia.org/wiki/File:1-over-x-plus-x.svg

    在此示例中，线 y = x 是 y = 1 / x + x 的渐近线，因为对于足够大的 x，两条线实际上合并。

    渐近复杂度以类似的方式表现，只是我们的计算复杂度依赖于元素的数量而不是图。

    因此，为了声称该算法具有O(1/N)的复杂度，算法的复杂度图必须与非常大的 n的 1/n 的图一致。但在这种情况下，1 / n退化为常数零。并且由于我们有一个常数，这意味着该算法具有恒定的复杂度，表示为O(1)。

    • 10

  3. 总的来说，有一个有趣的案例。在大多数情况下，说到渐近，我们假设参数增加。但是，严格来说，情况可能并非如此。例如，如果我们知道某个函数的范围是有限的。让我们int(1/x)通过减法来实现除法：

    function f(x) {
  for (var i=0, v=1; v>0; ++i, v-=x);
  return i;
}

console.log(f(1));
console.log(f(.5));
console.log(f(.25));
console.log(f(.125));
console.log(f(.0625));
console.log(f(.0000001));

    原则上，我们可以说这个函数是渐近的O(1/x)，即对于较小的 x 值，它会工作得很慢（顺便说一下，由于误差的累积，它也是不准确的）。当然，在整数参数的情况下，这个选项是不可能的。

    • 0

相关问题