algorithm - 如何使用求和符号证明算法是 Θ (log n)？

Question

假设我有以下代码:

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

你如何从数学上证明这是 Θ(log n)？

我通常的方法是使用求和(西格玛表示法)，但在这种情况下，我们不会线性增加循环变量。什么是好的方法？

Answer 1

i 的值为n, n/2, n/4, ..., 1。由于它是整数，因此在此条件下其最终值为 1。假设n为2^k，则迭代次数为k，即log n。因此情况没有改变，它是另一个具有一定迭代次数的for。

内部循环可以被认为是单个语句，因为 val 是常量。