algorithm - 以下代码片段的时间复杂度是多少？

Question

设 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)，但我在确定所有位为 0 或 0 或超过一半的位是 0，问题是函数的复杂性让我感到困惑，如果我试图忽略它那么复杂性将是 Θ(n) 本身，请指导我解决这个问题。

Answer 1

传递给 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)。