big-o - 所有条件检查都是常量大 O 吗？

Question

如果一个函数具有 O(N) 复杂度并且在 if 语句中调用它，它仍然是 O(1) 吗？

例如：

  f(x);
   if (f2(x))
     f3(x);

其中 f(x) 是 O(N) f2(x) 是 O(N) 而 f3(x) 是 O(Nlog2N)。

那么在条件为真的最坏情况下，这个片段的整体复杂度会是 O(Nlog2N) 吗？

Answer 1

Big O 返回算法时间复杂度或空间的上限（最坏情况）。

条件语句是 O(1)。

if (f2(x))可以写成

boolean b = f2(x);
if(b){...}

因此，上面的条件有 O(1)，而上面的 f2(x) 的评估是 O(N)。因此该集合将具有 O(N) 复杂度。

---

你会采取最坏的情况，即条件评估为真，然后计算它。 O(Nlog2N)将是您问题中块的整体复杂性。

（规则）

Answer 2

是的。这是最坏的情况。在一种情况下是 o(n)，而在另一种情况下是 o(N lg n)。

因此，由于我们对最坏的情况感兴趣，我们说它是后者。

Answer 3

Big-O 是一个上限，所以片段f1(); if(f2()) f3();是O(f1 + f2 + f3)。在不知道其他任何事情的情况下，这将是最好的结果（因为您必须假设最坏情况的行为）。

但是，如果可以证明这f2是错误的（例如，因为您在分析中已经到达数据结构的末尾），您可以将其缩减为O(f1 + f2). 这有时是必要的，例如在分析递归算法的基本情况时。