大規模なO操作数

Question

各コード行がどのように処理されるかをどのように計算しますか？

例。

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を設定する必要があるので、最初のループのように1 + n回の演算があります.jをarrLength - 1と比較するとn-1回ループします。したがって、n + 1 + 1 + 1の演算がn + 1回の演算になります。

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

私は、A[j][k] = xの比較で少し混乱しています。

ありがとうございました。あなたは、アレイ内のすべての要素の上に、（ログを掛け、あなたが繰り返し二つにアレイを分割するたびにN

掛けループ各時間について

：

Answer 1

Big-Ohは漸近的なので、 "1 + n"の "1"には注意しないでください。

あなたが探しているのは、そのコードのBig-Ohの分類です。単純に2つのループがあり、1つはループ内にネストされており、各ループは要素ごとに一定数の操作を実行していると考えてください。内部ループはO（n）であり、外部ループは内部ループをn回実行しているので、外部ループはO（n^2）です。関数全体はO（c + n^2）であり、ここでcは外部ループを取り囲むコードからの一定数の演算である。ビッグオーは漸近的なので、cは消え、あなたの関数はO（n^2）です。

コードで実行される操作の正確な数を計算しようとしている場合は、おそらく使用しているabstract machineを設定する必要があります。

これが役に立ちます。

Answer 2

一般的な経験則はこれですN）

配列全体に2つのネストループがあるので、あなたはO（N^2）です。

定数係数の計算は難しく、言語、コンパイラ、およびハードウェアの詳細に依存します。基本的には経験的にそれを動作させるだけです。

Answer 3

大きなOの点では、最も頻繁に発生する操作と最も頻繁に発生する操作を選択する必要があります。この場合、両方のループ内での比較です。繰り返しループの回数をカウントする必要はありません。最悪の場合に最も内側の部分が何回実行されるかを数えるだけです。外側ループの場合はn-1、内側ループの場合はn-1、合計はO(n^2)となります。