0

A を、0 と 1 を含む配列 [1..n] とし、func()を、複雑さが theta(m) である関数とします。与えられた疑似コードの複雑さは何でしょうか?

  counter=0;
    for(i=0;i<n;i++)
       {
          if(a[i]==1)
           counter++;
         else
           func();
   }

私によると、関数 func() が最大で n 回呼び出される最悪のケースは、配列が完全にゼロで埋められている場合です。したがって、 func() の theta 表記は theta(m) として与えられます。

上記のコードの複雑さは :theta(mn) ....??? になります。いいえの場合は、適切な検証を手伝ってください。

4

1 に答える 1

0

上記のコードの時間計算量はO(mn) (Big O mn)になります。
なんで？
あなたが言うように func() は theta(m) です。あなたが指摘したように、時間の複雑さを計算するとき、 func が n 回呼び出される最悪のケースは O(mn) になります。Theta(mn) ではないのはなぜですか? Theta は、時間計算量のより厳密な境界です。これは、常に最低でも mn* のパフォーマンスを発揮することを意味するだけでなく、最高でも mn* (* 乗法定数または加法定数を指定または取得) を実行することを意味します。したがって、入力に比例して増加します。ただし、omega(mn) の下限 (別名 omega) を保証することはできません。ビッグ オー vs ビッグ シータの詳細については、こちらを参照してください。


そして、なぜ私たちがシータ(mn)の下限を保証できないのか、あなたは答えられるはずです。

ベスト、Digvijay

于 2013-10-27T07:24:12.287 に答える