是否所有條件檢查都是恆定的大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

回答