for循环中if-else语句的时间复杂度

Question

设A[1, …, n]是一个数组，每个位置存储一个位（1或0），f(m)是一个时间复杂度为θ(m)的函数。考虑以下用类 C 语言编写的程序片段：

案例 1 :-

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

案例 2 :-

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

这个程序片段的复杂度是

(A) Ω(n2)

(B) Ω(nlog n) 和 O(n2)

(C) θ(n)

(D) O(n)

问题是我如何知道何时使用 if 语句或 else 语句以及何时调用 f(m) 函数，我该如何处理？我可以考虑仅执行 if 或仅执行 else 的情况，但是当有时执行 if 语句而有时执行 else 语句时的一般情况如何

Answer 1

我们可以从简单的情况开始，即情况 2。显然，每次我们通过情况 2 的循环时，都会发生以下两种情况之一：

计数递增（这需要 O(1) [除了 not really，但我们只是说它适用于在固定长度数字（即 32 位整数）上运行的计算机]）
count 设置为 0（这需要 O(1) [再次，值得商榷]）并且计算 f(count)（这肯定需要常数时间）

我们经过n次循环，每次实际花费O(1)时间，bada-bing，bada-boom，它需要O(n)（或O(n * lg(n )) 如果你很迂腐并且使用可变长度整数）。

另一方面，情况 1 需要一点数学思维。

情况1中耗时最短的位串显然是11111....11111、000....000、000...0111...111等。所有这些都需要 θ(n) 的时间来完成，为情况 1 建立一个下限。现在，我们需要建立一个最坏的情况。

在不进行适当证明的严格性的情况下，断言最坏情况的位串如下所示非常简单：

111....1110

上述形式的长度为 100 的位串将有 99 个 1，因此需要 99 + 99 个时间单位才能完成。长度为 n 的字符串显然需要 2(n - 1) 个时间单位才能完成。

这显然在 n 中仍然是线性的，所以情况 1，即使在最坏的情况下，也是 θ(n)。

因为case 1和case 2都是θ(n)，所以问题是θ(n)。

如果您仍然需要确信 11.....110 是最坏情况的位串，请考虑以下：

A bit string of the form
|--------------n bits------------|
1....101....101....10......1....10
|-L1-| |-L2-| |-L3-|       |-Lm-|
11110
Where L1 - Lm are arbitrary integers will require time 
t = (L1) + (L2) + (L3) + ... + (Lm) + (n - m)
  = sum(L1 to Lm) - m + n

the more "runs" of ones there are, the larger the - m factor is.  If we 
just have one big "run" of ones, we have

t = n - 1 + n - 1 = 2(n - 1)

作为一个 matter of principle，我不会在 Whosebug 上回答那些问得不好的家庭作业问题。

然而，在聊天中与 coder101 交谈后，he/she 告诉我这不是家庭作业问题，而是从网上检索到的问题数据库 here，旨在提供 "mock tests for geeks"。这看起来像是 coder101 给自己的挑战，虽然它可能是一个更好的问题，但我认为它没有那么糟糕。

for循环中if-else语句的时间复杂度

Time complexity of if-else statements in a for loop

if-statement

for-loop

time-complexity

asymptotic-complexity