このプログラムフラグメントの時間複雑度はどのくらいですか？

Question

counter = 0; 
for (i=1; i<=n; i++) 
if (a[i] == 1){ 
counter++; 
} 
else { 
f (counter); 
counter = 0;} 
} 

---

A[1, …, n]が各位置でのビット（1または0）を格納する配列であるとすると、f(m)は、その時間複雑θ(m)である関数です。

次に、このプログラムフラグメントの時間複雑度はどのくらいですか？

---

私は、アレイがすべてゼロが含まれている場合、それは継続的に呼び出されるよう、何が、機能f(0)の時間複雑になるという部分で立ち往生しています。

Answer 1

コードは常にTheta（N）です。 f(m)が一定のcに対してコストcmを持っているとしましょう。 f(m)はTheta（m）なので、実際には2つの異なる定数で上限と下限の解析を行うべきですが、分析はほぼ同じです。

次に、は、値1のランレングスに対応する値のあるシーケンスx1, x2, x3, ..., xkで呼び出されます。 fの呼び出しの総コストはc*x1 + c*x2 + ... + c*xk = c(x1 + x2 + ... + xk)です。 (x1 + x2 + ... + xk)は配列内の1の合計数であるため、この合計は最大でN（配列の長さ）です。したがって、fを呼び出すための総コストは常にO（N）になります。

コードは常にN回ループするため、Nも総コストの下限です。

これは線形の上限と下限を示しているので、fはTheta（N）です。