時間のif文と

Question

だからこの質問を解決しようとイムループの入れ子になったとアルゴリズムの複雑さが、私と私の友人は少し私は外側のループがOであることを取得

for (Int64 i = 1; i < Math.Pow(2, n); i = 2*i) 
{ 
    if (i <= 4 || i >= Math.Pow(2, n - 2)) 
    { 
     for (Int64 j = n; j >= 0; j = j - 2) 
     { 
      //constant number of C operations 
     } 
    } 
    else 
    {  
     for (Int64 j = n; j > 1; j = (Int64) Math.Ceiling((double) j/2)) 
     { 
      //constant number of C operations 
     } 
    } 
} 

それによって混乱している（N）私は内側部分が何であるかを知ることができません、私はそれがちょうどO（n）であることを確信しています。 log n）。
これは正しい考えですか？または私は間違っています

Answer 1

しかし、私は内側部分が何であるかを知ることができませんが、私はループの内側の最大のO（n）からO（n） O下部一方に並置として

上部内側のループは、実際Θ（N）ある（ログn）。少なくともしない意味で使用すると、全体としてΘ（N を取得外側ループのΘ（N）、ことによって、これを掛ける必要があることを、内側部分は、Θ（N）であるということにはなりません）。これは、内部のトップループが一定回数だけ実行されるためです。上部内側ループのΘ（n）は、外側ループのそれに加えて、をに追加する必要があります。

このコードの全体的な複雑さは、Θ（n log（n））です。具体的には、Θ（N）Θ（）N（ログ）（完全底内側ループを実行するの総複雑さ）+ Θ（N）+ Θ（N）完全上部内側のループを実行する（合計複雑です）。