ネストされたforループをO（n^3）よりも低く変換する

Question

したがって、私はこのコードを持っており、O（n^3）未満の時間の複雑さで実行する必要があります。私は複雑さについて学び始めたばかりなので、何をすべきか分かりません。

int n, i, j, k, x=0; 
printf("Type n: \n"); 
scanf("%d",&n); 


for(i=1; i<n; i++) 
{ 
    for(j=1; j<i; j++) 
    { 
     for(k=1; k<j; k++) 
     { 
      x=x+1; 
     } 
    } 
} 
printf("%d\n",x); 

私はそれはO（N^3）だ、なぜ私が得ると思いますが、私は実際にそれをより効率的にする方法がわかりません。再帰関数に変換しようとしましたが、可能でしょうか？

Answer 1

0、k <、<、< nの各i、j、kの結果に1を加算しています。 i、j、kの値（{1,2、...、n-1}のサイズ3の各サブセットに1つ）を選択（n-1、3）する。 （ここでは、二項係数関数で「選択」します）。

したがって、ループベースの計算は、の場合は(n - 1)(n - 2)(n - 3)/6のchoose（n-1、3）に置き換えることができます（nが正の場合）。

int n; 
printf("Type n: \n"); 
scanf("%d",&n); 
printf("%d\n", n > 0 ? (n-1)*(n-2)*(n-3)/6 : 0); 

（結果はO（Nログ）数字があるので）これを出力するO（1）の結果を計算するため、及びO（Nログ）です。

Answer 2

あなたの現在の機能は、いくつかの数学関数を計算するだけのお粗末なO(n^3)方法です...

In Out 
0 0 
1 0 
2 0 
3 0 
4 1 
5 4 
6 10 
7 20 
8 35 
9 56 
10 84 

xは、繰り返しの数に等しいことになります。

あなたの割り当てはforループを方程式に再解釈する可能性があります。

外部ループはブロック(n-1)回を実行することがわかります。次の内部ループはブロックの合計を1+2+..+(n-2)回実行します。 That's(n-1)(n-2)/2回。 が

別の方法（この時点で私は自分自身をはまり、私の外挿のいずれもが（N-1）（N-2）（N-3）/ 6を取得していない）：私たちが知っているので1、2、3というすべて0のルーツであり、我々はまた、の関数が少なくともであることが、(n - 1)(n - 2)(n - 3)であることを知っている。 n=4を解くと、定数因子として1/6が得られます。

Answer 3

次のように私はあなたのループをリファクタリング：

for(i=1; i<n-2; i++) 
{ 
    x = x + ((i * (i + 1))/2); 
} 

これはシリーズI 1〜内のすべての値のため((i * (i + 1))/2) =合計を動作します。

内部のループ（変数kを使用）は、jの値をxに加算するのと同じです。 2番目のループ（変数jを使用）は、系列1から系列iの合計を計算することと等価です。

私は2番目と3番目のループをシリーズ1〜iの合計で置き換えました。私たちはあなたの最初のループを維持し、各反復でシリーズ1〜iの合計を以前の値に加算します。

外側ループに-2を追加して、2つの内側ループの<記号をシミュレートしました。あなたの要件が各内側のループに< =だったら、-2は必要ありません。

これはO（n）ソリューションで、Paul Hankin's O(1) solutionほど良くありません。