バブルソートの複雑さの分析

Question

多分、この質問は何度も聞かれましたが、私は疑いがあります。次のアルゴリズムでは：

BubbleSort(v[n]) 
i←0 
exchange←V 
while (exchange) 
    exchange←F 
    i←i+1 
    for pos=0 to n-i 
     if v[pos]>v[pos+1] then 
      swap(v[pos],v[pos+1]) 
      exchange←V 
     endif 
    endfor 
endwhile 

私はこのようにそれを分析した：

が、私は正しいことを行っている場合、私は私ができる内側のループを分析する場合ので、私は、疑問を持っています私が持っていると言う：

私はcがループしながら、外の値に依存していると言うことができ

、それがアクティブであるかどうかに関わらず、ここで概説した両方の分析がより正確です。

ありがとうございました

Answer 1

両方の分析が間違っています。

最初の分析では、外の合計を削除すると、合計内の式を、それがないときの合計変数とは独立したものとして扱います。それ以降のあなたの仕事はiを定義した合計が削除されてもそれにはiが含まれています。間違ったことをしたことを明確に示しています。

...の後に2回目の分析では、cを忘れてしまいます。