0

アルゴリズムの本でこのコードを見つけましたが、例を理解できませんでした。

コードは次のとおりです。

for(i=1;i<n-1;i++){
   for(j=n;j>i+1;j--){
      if(a[j-1]>a[j]){
         t=a[j-1];
         a[j-1]=a[j];
         a[j]=t;
    }
  }
}

今、本によると、このように計算された各部分の複雑さこれ

また、このように計算されたコード全体の大きなOこれ

しかし、私はそれを理解できませんでした。このコードの複雑さを説明してもらえますか? 特にO(n/2)用語のせいで複雑さを計算した部分j>i+1

4

2 に答える 2

0

外側のループは i=1 から n-2、つまり n-2 回実行します。内側のループは (n-3), (n-4),......, n-(n-1) を実行し、合計で n-3+n-4+n-5+...+ 2+1回。i=1 の場合、内側のループは (n-3) 回実行され、i=(n-2) の場合、内側のループは 1 回実行されます。これにより、(n-3) (n-2)/2 が得られます。if 条件とその本体を考慮すると、内部ループの実行ごとに 3 つのステートメントが実行されます。合計すると、(n-3) (n-2)/2 * 3 になります。(n-3) を (n-3) と見なす必要はありません。および/2。このような方法を使用した複雑さの計算は近似値です。したがって、複雑さは n*n のオーダーです。O(n^2)。

ループが表示されたら、それを n ステップと見なします。内部ループがある場合は、それを乗算します。1 ループの場合 O(n)。2 つのループの場合 O(n*n)。3 つのループの場合 O(n**n*n) など

于 2017-06-20T07:40:51.263 に答える