1

プロジェクトの時間の複雑さを計算しようとしています。ループがこのようなものである場合、誰かが複雑さを計算する方法を教えてくれますか?

while (k < K){

    for( int i=0; i<M; i++){

        // if condition
        // sets i = dp
    }

    for(int i=dp; i<M; i++){

        for(int j=0; j<=i; j++){

            // single stmt
        }

        // if else condition
        function call(); // assume this has complexity of N
    }
    k++;
}

また、ストレージ スペースの複雑さを特定する方法について、いくつか提案をお願いします。

4

3 に答える 3

1

時間計算量は、コードが実行する反復回数によって計算されます。したがって、コードを分析すると、最上位のループが K 回繰り返されるため、最初の複雑さは K になります。次に、そのループ内に複数のループがあり、ネストされた各ループの複雑さが最上位のループで乗算されます。したがって、最上位ループ内には 2 つの for ループがあり、1 つは複雑度 M で、もう 1 つは内部にネストされたループがあり、そのループの複雑さが M*j になります。呼び出された関数の N したがって、コード全体の複雑さをすべて足し合わせると、K* (M+(M*(j+N)))になります。

  • K -> 最初にトップレベルのループ
  • M - > 最初のネストされたループ
  • M * (j+N) -> ネストされたループと関数呼び出しを含む 2 番目のネストされたループ
于 2013-06-05T14:35:28.127 に答える
1

このコードの複雑さは K* (M+(M*((M*M)/2+(M/2)+N))

  K-times for while loop
  M-times for first for loop
  M*((M*M)/2+(M/2)+N) - for nested for loop

ネストされた for ループが半分の行列を生成する例

  1
  11
  111
  1111

完全な行列の複雑さはM*M半分の行列になるので ( M*M)/2 + 対角線全体を追加する必要があります(M/2)

于 2013-06-05T14:29:40.130 に答える
0

このコードの複雑さは K* (M+(M*(M+N)) であり、これが最大の可能性です。

しかし、それでもあなたのコードによれば、複雑さを軽減できる dp が i に設定されているものにも依存します。

それならありえる

このコードの複雑さはK*(M+(M*((M-dp) + N)) になります。

于 2013-06-05T14:46:18.940 に答える