是O（n^2）还是O（1）？

Is the execution time of this unique string function reduced from the naive O(n^2) approach?是O（n^2）还是O（1）？

这个问题有很多有趣的讨论，使我怀疑，如果我们把一些门槛上的算法，它会改变大O的运行时间复杂性？例如：

void someAlgorithm(n) { 
    if (n < SOME_THRESHOLD) { 
     // do O(n^2) algorithm 
    } 
}

它会为O（n 2 ）或会是O（1）。

来源

2015-05-21 invisal

您的代码段中是否存在'else'条件？如果你没有执行超过硬编码有限值的任何内容，那么运行时间将受常数限制。 –

这将是O(1)，因为有一个常数，所以无论输入多大，算法都会在小于该常数的时间内完成。

从技术上讲，它也是O(n^2)，因为有一个恒定的c，所以无论输入多大，算法都会在c * n^2时间单位内完成。由于大O为您提供了上限，一切是O(1)也O(n^2)

来源

2015-05-21 03:27:39 Ishamael

如果SOME_THRESHOLD是恒定的，那么你已经硬编码的恒定上限函数的增长（f(x) = O (g(x))给出了一个上限的g(x)对f(x)的增长）。

按照惯例，O(k)对于一些常数k只是O(1)，因为我们不关心常数因素。

请注意，下限是未知的，至少理论上是这样，因为我们不知道O(n^2)函数的下界。我们知道f(x) = Omega(h(x)),h(x) <= 1是因为f(x) = O(1)。小于恒定时间的功能是可能的in theory，虽然在实践中h(x) = 1，所以f(x) = Omega(1)。

这一切意味着什么，通过强制函数的常数上界，函数现在有一个严格的界限：f(x) = Theta(1)。

来源

2015-05-21 04:01:20 Anthony

根据计算模型，你可能实际上有f（n）= Theta（0） –

是O（n^2）还是O（1）？

回答

相关问题