快速算法复杂度计算

Question

我熟悉 Big O 的东西并且通常知道如何使用关键部分来计算复杂性。这个给了我一点工作，所以我喜欢一个答案和一个小的解释：

i = 1;
while(i<= n){
   if(i%2 == 0)(
   System.out.println(i);
   }
   i++;
}

据我了解，if 的正文将 运行 n/2 次，因为只有偶数 i 会打印出来。整体复杂性也是如此： 1+ (n/2) 使 Big O O(n)?`

Answer 1

整体复杂度为n + n/2 *（System.out.println(i);的复杂度）。在这种情况下，我认为您可以假设调用 System.out.println 的复杂度是恒定的，因此整体复杂度为 O(N)。仍然需要注意的重要一点是，您不能忽略迭代的复杂性。

Answer 2

总体复杂度仍然是 O(n)，因为检查 i%2 的值并递增 i 它仍然算作工作。执行 n/2 次的 if 语句的主体只是增加了额外的 O(n) 工作量。

Answer 3

您误解了代码的 body 到底是什么（而不是循环的主体）。这是你的代码（/循环）的主体：

if (i%2 == 0) {
   System.out.println(i);
}
i++;

并且这个主体将被执行总共 n 次，即使有一半的时间 if 条件会失败。