是否所有条件检查都是恒定的大O？

如果一个函数有一个O（N）复杂度并且它在if语句中调用，它仍然是O（1）？是否所有条件检查都是恒定的大O？

例如：

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

其中f（x）为O（N）F 2（x）是O（N）和F3（x）是O（Nlog2N）。

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

2012-10-21 nitiger

是。这是最坏的情况。在一种情况下，它是o（n）和其他情况o（n lg n）。

所以，既然我们对最坏的情况感兴趣，我们说它是后者。

2012-10-21 05:05:22 smk

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

条件语句是O（1）。

if (f2(x))可以写成

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

所以，在上述条件，具有O（1），而f2的评价（x）的以上是O（N）。所以这个集合将会有O（N）的复杂性。

你会采取最坏的情况，条件评估为真，然后计算它。 O（Nlog2N）将是您问题中该块的总体复杂度。

2012-10-21 05:03:06

而条件只是O（1）或O（N）？ – nitiger

把它写成等价的 'bool cond = f2（x）;如果（cond）{...} ' –

if语句的整体复杂度将是'O（1）+ O（N）'，即'O（N）'。 –

Big-O是一个上限，所以片段f1(); if(f2()) f3();是O(f1 + f2 + f3)。如果不知道别的什么，那将是最好的结果（因为你必须承担最坏情况的行为）。

但是，如果能证明那是f2假的（例如，因为你已经到了一个数据结构的结尾在你的分析），你可以把它删减到O(f1 + f2)。这有时是必要的，例如在分析递归算法的基本情况时。

2012-10-21 05:05:55 nneonneo

回答