我将如何计算此算法的 big-O

Question

我有这个算法

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

我说的 Big-O 是 n/2 对吗？

Answer 1

你说得对！这基本上是一个商为 2 的几何级数，元素的数量为 lg(n)，因为我们将 i 除以 2 每次外循环迭代。

1, 2, 4, ..., n

使用已知公式计算总和，我们得到：

我们有 lg (n) 个元素的原因是因为我们将 i 每次迭代除以 2，因此我们需要求解迭代次数 k:

Answer 2

TL;DR时间复杂度为O(n).

更多详情

Am I right in saying that the BigO for this would be n/2?

不准确，在大 O 表示法中，您删除常量部分，因此 (1/2)n 简化为 O(n)。

我不确定 n/2 来自哪里，因为只有外循环

for(int i = n; i >= 1; i = i/2) {
   ...
}

是log2n而不是n/2。

并且两个循环一起：

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

计数会在 N 和 2N 之间变化。

让我们计算一下：

int count = 0;
for(int i = n; i >= 1; i = i/2) {
   for ( int j = 1; j <= i; j++) {
      count++;
   }
}

内部循环将执行 N 次迭代，然后 N/2，然后 N/4 ... 直到 N/N.

换句话说，我们有 (N + N/2 + N/4 ... N/N)，可以简化为 N * (1/2 + 1/4 + .. + 1/2^L))，L = Log2 N。

这个(1/2 + 1/4 + .. + )系列is well-known for being 1。因此，我们可以将N * (1/2 + 1/4 + .. + 1/2^L))简化为O(N).

How would I calculate big-O for this Algorithm