2つのループで実行時間O（n^3 log n）で実行

Question

私はこれをしばらく理解しようとしており、私はそれを得ることができません。どんな助けも素晴らしいだろう。私はC++でプログラミングしています。

2つのループ構造を使用して、O（n^3 log n）の実行時間を見つけます。

Answer 1

がヒントです：あなたがする必要がありますO(N*LogN)操作を2つのネストされたループの中に入れて、操作にループが必要ないようにします。

たとえば、N項目の配列で開始することができるiとiとj間の配列要素を逆jにネストされたループを実行し、次いで得られた配列をソート。反転はO(N)、ソートはO(N*LogN)なので、ソートが支配的です。 2つの外部ループは残りのO(N^2)を提供します。ソートとリバースの両方を、追加のループなしで、標準ライブラリ関数を使用して行うことができます。

Answer 2

私はおそらくこれを知っているが必要とされるものではなく、単にポイントを作るために - あなたはこれを行うことができます：ここで、これは宿題であると仮定すると

int x = 0; 
for (int i=0; i<n; ++i) { 
    for (int j=0; j<n*n*log(n); ++j) { 
    x += j; 
    } 
} 

Answer 3

ほとんどすべての種類の複雑さは、本当にただ1つのループ構造で実現できるようです。あなたのケースでは、（擬似コード）のようなもの：

a := 0 
b := 0 
c := 0 
d := 1 
WHILE a < n OR b < n OR c < n OR d < n LOOP: 
    a := a + 1 
    IF a = n THEN: 
     a := 0 
     b := b + 1 
     IF b = n THEN: 
      b := 0 
      c := c + 1 
      IF c = n THEN: 
       c := 0 
       d := d * 2