c - 寻找递归关系和复杂性

Question

根据操作次数，找出递归关系!

a = N;
var = 0;
while (a > 1) 
{
var = var + a; 
num = 2 * var; 
a = a / 2;
}

我认为会形成的递归关系是:(赋值操作不算)

T(n)= (from a=1 to N)Σ(3)

我说得对吗？？

现在使用这个递归关系，如何找到它的复杂性。

Answer 1

你想要做的是找到这个操作被调用了多少次，所以考虑这个:在每次调用之后 a 除以 2，所以如果 M = N/2 那么 T(M) = T(N) - 1 .

现在，此循环的每次迭代都会再次除以 N，因此您会得到以下结果:

T(N) = T(N/2) + 1 = ... = k + T(N/(2^k))

停止条件是这样的:a>1所以你需要检查什么时候 N/(2^k) <= 1

N/2^k = 1 -> log (n) = k

所以 T(N) = log(n) + T(1) = log(n)

这是“大 O”表示法的答案。