1

コードの各行に必要な操作の数をどのように計算しますか。

例。

Algorithm find2D (A,x)
    arrLength = A.length
    for j <- 1 to arrLength – 1 do
         for k <- 1 to arrLength – 1 do
                if A[j][k] = x then
                  return true
          increment k
    increment j
return false

この疑似コードを思いつきました。そのため、コードの各行にかかる操作の数を数える方法がよくわかりません。

j を設定し、j を arrLength - 1 と比較する必要があるため、最初のループは 1+n 操作になり、n-1 回ループします。これにより、n+1 操作である n-1 + 1 + 1 が得られます。

したがって、2 番目のループでは、ネストされていても同じことになります。

私はA[j][k] = x比較について少し混乱しています。それは何回の操作になるでしょうか。

ありがとう。

4

3 に答える 3

2

一般的な経験則は次のとおりです。

配列内のすべての要素をループするたびに、N を掛けます

配列を繰り返し 2 分割するたびに、log(N) を掛けます。

配列全体に 2 つのネストされたループがあるため、O(N^2) になります。

定数係数の計算はより複雑で、言語、コンパイラ、およびハードウェアの詳細に依存します。基本的には経験的にそれを解決する必要があります。

于 2011-01-20T21:23:18.353 に答える
1

Big-Oh は漸近的であるため、「1+n」の「1」は気にする必要はありません。

探しているのがそのコードの Big-Oh 分類だけである場合は、2 つのループがあり、一方が他方の内部にネストされており、各ループが要素ごとに一定数の操作を実行していると考えてください。次に、内側のループは O(n) であり、外側のループは内側のループを n 回実行しているため、外側のループは O(n^2) です。次に、関数全体は O(c+n^2) です。c は、外側のループを囲むコードからの操作の定数です。Big-Oh は漸近的であるため、c が消え、関数は O(n^2) になります。

コードが実行する操作の正確な数を計算しようとしている場合は、おそらく、使用している抽象マシンを確立する必要があります。

お役に立てれば。

于 2011-01-20T21:31:52.330 に答える
0

大きなOに関しては、カウントする操作を選択する必要があります。最も頻繁でアトミックな操作です。この場合、それは両方のループ内の比較です。反復するためにループが実行している比較の数を数える必要はありません。最悪の場合、最も内側の部分が実行される回数を数えるだけです。合計を与えるn-1のは、外側のループ用であり、それぞれ内側のループ用です。n-1O(n^2)

于 2011-01-20T21:26:09.610 に答える