这个程序片段的时间复杂度是多少？

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有成本厘米。真的应该用两个不同的常量进行上下限分析，因为f(m)是Theta（m），但分析或多或少会相同。

然后，f被调用一些值序列，x1, x2, x3, ..., xk，它们对应于1的游程长度。调用f的总费用是c*x1 + c*x2 + ... + c*xk = c(x1 + x2 + ... + xk)。由于(x1 + x2 + ... + xk)是阵列中1的总数，所以该总和最多为N（阵列的长度）。因此致电f的总费用将始终为O（N）。

该代码总是循环N次，所以N也是总成本的下限。

我们已经展示了线性上下界，所以f是Theta（N）。