複雑、ハーフ各反復

Question

void G(....) 
{ 
    for (int k = n/2; k > 0; k /= 2) 
    { 
    for (int m = 0; m < n; m++) 
     a[(k+m)%n]=k+m; 
    }      
} 

ことで、私はループイニシエータと増分はそうで(n/2)と(k/=2) respectively..andのようなものであるとき、ループ処理をカウントする方法がわかりませんよ。このコードをnの異なる値に対してコンパイラで実行すると、nが2^xの場合、2 ^（x + 1）-1までのnの値はn * xとなるなど、興味深い結果が得られました。今私は立ち往生しており、これをどのように分類するのかBig Ohの機能が分からない。すべての回答/フィードバック/推奨される学習方法/説明を歓迎します！

Answer 1

外側ループは、 k = n/2、n/4、n/8、...、*の間実行されます。それは連続的な分割により1 N/2を低減するために必要な順序で2

によってKの各値に対して、無関係に - それは完全Θ（ログ（N））回実行します内部ループはn回実行されるので、内側ループ+ボディはΘ（n）時間で実行されます。

外部ループの値に関係なく内部ループ+ボディが同じ時間を取るため、外部ループの実行回数に内部ループ+本体の実行時間を掛ける必要があります。これはΘ（n log（n））です。