algorithm - 償却された複雑さと最悪の場合の時間の複雑さとの関係

Question

私は、それぞれがO(1)の償却された複雑さで実行されるn個の連続した操作のセットを持っています。セット全体が O(n) の最悪の場合の時間の複雑さで実行されていると言えますか? どうやって証明するの？

Answer 1

コードサンプルを提供しなかったので、n 個の連続した操作をアルゴリズムの for ループと見なします。したがって、タスクは、最悪の場合の複雑さを見積もることです

for(int i=1; i<n; i++)
{
   f(x) // O(f(x)) = O(1)
}

言い換えると

Sum(1,n) 1 = O(1) + O(1) + ... O(1) //n-times

また

O(1) + O(1) + ... O(1) = O(n)O(1) = O(n)