假设我有以下代码:
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)?
我通常的方法是使用求和(西格玛表示法),但在这种情况下,我们不会线性增加循环变量。什么是好的方法?
最佳答案
i
的值为n, n/2, n/4, ..., 1
。由于它是整数,因此在此条件下其最终值为 1。假设n
为2^k
,则迭代次数为k
,即log n
。因此情况没有改变,它是另一个具有一定迭代次数的for
。
内部循环可以被认为是单个语句,因为 val
是常量。
关于algorithm - 如何使用求和符号证明算法是 Θ (log n)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42193633/