big-o - すべての条件付きチェックは常に Big 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) になるのでしょうか?

score 1 · Accepted Answer

Big O は、時間の複雑さまたはアルゴリズムの空間の上限 (最悪のシナリオ) を返します。

条件文は O(1) です。

if (f2(x))次のように書くことができます

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

したがって、上記の条件式は O(1) ですが、それより上の f2(x) の評価は O(N) です。したがって、コレクションの複雑さは O(N) になります。

条件付きで true に評価されるという最悪のケースを取り、それを計算します。 O(Nlog2N)は、質問のブロックの全体的な複雑さになります。

score 1 · Accepted Answer

はい。最悪のシナリオです。ある場合は o(n) で、他の場合は o(N lg n) です。

したがって、私たちは最悪のケースに関心があるので、それは後者であると言います。

score 0 · Accepted Answer

Big-O は上限なので、フラグメントf1(); if(f2()) f3();はO(f1 + f2 + f3). 他に何も知らなくても、それが可能な限り最良の結果になります (最悪の場合の動作を想定する必要があるため)。

しかし、それが誤りであることを証明f2できる場合(たとえば、分析でデータ構造の最後に到達したため)、それをに切り詰めることができますO(f1 + f2)。これは、再帰アルゴリズムの基本ケースを分析する場合などに必要になることがあります。

3 に答える 3