這個程序片段的時間複雜度是多少？

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）。