以下代码片段的时间复杂度是多少？
what is the time complexity of below code fragment?
设A[1, …n]是一个数组，每个位置存储一个位（1或0），f(m)是一个时间复杂度为Θ(m)的函数。考虑以下用类 C 语言编写的程序片段：
counter = 0;
for (i=1; i<=n; i++)
{ if a[i] == 1) counter++;
else {f (counter); counter = 0;}
}
我只能处理所有位都为 1 的最佳情况，因此时间复杂度将为 Θ(n)，但我在确定所有位都为 1 时会发生的最坏情况时感到困惑0 或超过一半的位是 0，问题是函数的复杂性让我感到困惑，如果我试图忽略它那么复杂性将是 Θ(n) 本身，请指导我解决这个问题。
传递给f的所有计数器的总和最多为n，因此调用f的总成本为O(n)。这是因为 f(m) 具有时间复杂度 Theta(m)，这意味着某些 c 的成本 f(m) < c*m，因此可以将调用 f 的成本限制为输入 m_1、m_2, ..., m_k 通过 c*(m_1 + m_2 + ... + m_k).
每次循环都会完成一些工作，因此总成本也低于 n 的倍数。因此总成本为 Theta(n).
设A[1, …n]是一个数组，每个位置存储一个位（1或0），f(m)是一个时间复杂度为Θ(m)的函数。考虑以下用类 C 语言编写的程序片段：
counter = 0;
for (i=1; i<=n; i++)
{ if a[i] == 1) counter++;
else {f (counter); counter = 0;}
}
我只能处理所有位都为 1 的最佳情况，因此时间复杂度将为 Θ(n)，但我在确定所有位都为 1 时会发生的最坏情况时感到困惑0 或超过一半的位是 0，问题是函数的复杂性让我感到困惑，如果我试图忽略它那么复杂性将是 Θ(n) 本身，请指导我解决这个问题。
传递给f的所有计数器的总和最多为n，因此调用f的总成本为O(n)。这是因为 f(m) 具有时间复杂度 Theta(m)，这意味着某些 c 的成本 f(m) < c*m，因此可以将调用 f 的成本限制为输入 m_1、m_2, ..., m_k 通过 c*(m_1 + m_2 + ... + m_k).
每次循环都会完成一些工作，因此总成本也低于 n 的倍数。因此总成本为 Theta(n).