loops - ネストされたループの複雑さ

Question

Big O表記を使用してforループの複雑さを理解しようとしています。以前に他のクラスでこれを行ったことがありますが、これは実際のアルゴリズムに基づいているため、他のクラスよりも厳密です。コードは次のとおりです。

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

と

for(i=1 ; i<=n;i++,x=1) //for any size n
{
    for(j = 1; j <= i; j++)
    {
      for(k = 1; k <= j; x+=a,k*=a)
      {

      }
    }
}

最初のループは、リストを n 回通過するため、O(n) の複雑さであることがわかりました。2 番目のループについては、少し迷っています。分析にご協力いただきありがとうございます。各ループは独自の空間にあり、一緒ではありません。

Answer 1

次のように正式に進めることができます。

フラグメント 1:

フラグメント 2 (Pochhammer、G 関数、およびスターリングの近似) :

log(G(n))で。

[フラグメント 2 の更新] :

Johann Blieberger 博士による「DISCRETE LOOPS AND WORST CASE PERFORMANCE」出版物からのいくつかの機能強化 (すべてのケースがa = 2で検証済み):

どこ：

したがって、

Answer 2

編集: 最初のコード ブロックがO ( n )であることに同意します

i外側のループを 2 で割ることによってデクリメントし、内側のループで時間を実行iすると、反復回数は、N 以下で 0 より大きい 2 のべき乗すべての合計になります。つまり、n ^{log( n)+1} - 1 なので、O (n) です。

2 番目のコード ブロックはO (log _a (n)n ² )aであり、 は定数であると仮定します。

最も外側の 2 つのループは、n 以下のすべての数の合計 (n(n-1)/2) に等しいため、O (n ² ) になります。最後に、内側のループは n の上限よりも小さい a の累乗であり、これはO (log _a n) です。