for（）ループがif（）文内にある場合、ランタイムはどのように影響を受けますか？

Question

は、我々はこのコードを持って言う：

doSomething(int n) { 
    for(int i = 0; i < n; i++) { 
     if (i % 7 == 0) { 
      for(int j = 0; j < n; j++) { 
       print("*"); 
      } 
     } 
    } 
} 

（図示証明/仕事に）大きな-Oとビッグオメガランタイムは何ですか？ 私の心はif（）ステートメントとbig-omegaを証明する方法から吹き飛ばされています（big-Oのために上限だから条件を無視することができます）。 何か助けていただければ幸いです。ありがとう！

Answer 1

まず、ランタイムをより明確に公開する方法で、物事を書き直してみましょう。例えば、内側のループは、（n）はΘのランタイムを持っていること、それでは、このようなコードを書き直してみましょう：

今

for(int i = 0; i < n; i++) { 
    if (i % 7 == 0) { 
     do Θ(n) work 
    } 
} 

は、このループが実行されるときに何が起こるかを考えます。 7回の反復のうちの1回がその内側のループをトリガーし、Θ（n）を実行し、残りの6/7は反復ごとに動作せず、Θ（1）を実行します。これが行われ、合計作業が

N（（1/7）× Θ（N）+（6/7）× Θ（1））

= N（Θ（N）+であることを意味しますΘ（1））

= N（Θ（N））

= Θ（N ）。すなわち

、ここで行わ全仕事はΘ（N ）です。基本的に、if文は1/7のファクタで行われる作業を減らすだけであり、big-O表記は定数を無視しているので、これも意味があります。あなたが最初にこのコードの問題書かれていた

---

：

for(int i = 0; i < n; i++) { 
    if (n % 7 == 0) { 
     for(int j = 0; j < n; j++) { 
      print("*"); 
     } 
    } 
} 

はここに私のオリジナルの答えです：

がのがより明確にランタイムを公開する方法で物事を書き換えしようとすることから始めましょう。内側のループはΘのランタイム（n）を持っていること、例えば、それでは、このようなコードを書き直してみましょう：

for(int i = 0; i < n; i++) { 
    if (n % 7 == 0) { 
     do Θ(n) work 
    } 
} 

それではここで何が起こっているかについて考えてみましょう。起こる可能性には2つの可能性があります。まず、nが7の倍数である場合があります。その場合、if文が毎回トリガされ、n回の外部ループ反復のそれぞれでΘ（n）が動作します。したがって、最悪の場合に行われる作業の合計はΘ（n ）となります。 nが大きくなるにつれて、私たちはより多くの7の倍数を実行し続けるので、私はその境界を締め付けることができません。第2に、nが7の倍数でない場合があります。その場合、Θ（n）ループの繰り返しをすべて実行するとΘ（1）がそれぞれ動作するため、ベストケースでは合計作業をΘ（n）とします。

全体的には、これは最悪の場合には、我々はΘ（nは）作業を行うと、最良の場合には、我々はΘ（n）の作業を行うことを意味します。したがって、関数のランタイムはO（n ）とΩ（n）であると言うことができますが、最善と最悪の場合のランタイムのより正確な記述は少し有益です。

ここでの分析の鍵は、if文が常に発火するか、発火しないかのいずれかを実現することです。これにより、推論を2つの別々のケースに分けやすくなります。

big-O分析は、たくさんのものを一緒に乗算することだけではないことに注意してください。それは、プログラムを実行する場合にプログラムが実際に行うことを考えてから、ロジックがどのように機能するかを考えることです。このようにbig-O分析に近づけば、時間を無駄にすることはほとんどありません。