2

次のループの実行時間を見つけようとしています。

int m=1;
for(i=1;i<=k;i++)
{
    for(j=1;j<=A[i];j++)
    {
        B[m]=i;
        m++;
     }
}

ここで、Aは整数を保持する配列であり、これらの整数の合計はnです。たとえば、Aの長さが2で、A [1]=2およびa[2]= 4の場合、内部ループは6回実行されます。

したがって、私の講義ノートでは、このコードの実行時間はO（n + k）であると書かれています。ただし、たとえば、kが5、配列Aの長さが4、A [1] = 3、A [2] = 0、A [3] = 0、A [4] = 9、A[ 5]=0。したがって、n=12です。次に、k = 1の場合、内側のループは2回繰り返され、k = 2の場合、外側のループは1回繰り返され、k = 3の場合、外側のループは1回実行され、k = 4の場合、内側のループは9回実行されます。 k = 5の場合、外側のループは1回実行されるため、反復の合計は14です。これはkとnの両方より大きく、実行時間はO（n）でもO（k）でもありません。私はここで何が間違っているのですか？

ありがとうございました

4

2 に答える 2

3

あなたがやっているので、外側のループはk回繰り返されます

for(i=1;i<=k;i++)

内側のループの総反復回数は

sum (A[i])、i = 1...kあなたが知っているのは= nです。

それはn + k反復を与えます。内側のループ内のものは一定時間で実行されるため、複雑さはO(n + k).

編集：

非負関数f(n)がであると言うとき、私たちは何を意味しO(g(n))ますか?

答え：

適切な Stackoverflow の質問を検索します

「Big O」表記の分かりやすい英語の説明は?

EDIT2：

実際、上記のリンクの回答は非常に冗長であるため、完全を期すために、数学的な定義を次に示します。

f(n)非負関数とします。次に、 (「f(n) は g(n)のf(n) = O(g(n))ビッグ オー」と読みますc)n0

f(n) <= c g(n)

すべてのためにn >= n0。

于 2013-03-22T19:28:52.110 に答える