假设我有以下代码:
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)?
我通常的方法是使用求和(sigma表示法),但是在这种情况下,我们不是线性地增加循环变量。有什么好的方法呢?
的值i
是n, n/2, n/4, ..., 1
。由于它是整数,因此在这种情况下其最终值为1。假设n
为2^k
,则迭代次数k
为log n
。因此,情况不会改变,这是for
具有一定迭代次数的另一种情况。
内部循环可以视为单个语句,因为它val
是恒定的。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句