1

Nだけでなく2つの変数が関係している場合、次のネストされたループの時間の複雑さを表す方法は?

N = サイズの入力としましょう A = 離散値 (関連する数量)

したがって、N=50000 および A=30000 の場合

for( int i=0;i<N;i++)
{
    for( int j=0;j<A;j++ )
    {
       for( int x=0;x<N;x++)
       {
          // do something
          doSomething();
       }
    }
}

O(N^2*A) でしょうか?

前もって感謝します

4

2 に答える 2

0

はい、あなたの場合の複雑さはO(N^2*A)

于 2013-08-12T18:52:51.257 に答える
0

はい、O(A*N^2)です。時間の複雑さに個別に影響する場合は、下位の項のみを無視します (つまり、「O(A + N^2)」は O(N^2) になります)。

于 2013-08-12T18:54:42.563 に答える