寻找递归关系和复杂性

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)

这是 'big O' 表示法的答案。

Answer 2

实证方法：

首先通过简化代码减少"educational noise"，并添加一个迭代计数器(c)。然后查看结果 (N,count)，一段时间后您会看到，对于 [1,2,4,8,16,..] 中的所有 N，2 ^ count = N。

所以复杂度 Compl(loop) = O(log_2(N)).

let rec loop a c = 
    match a with
    | x when x > 1 -> 
        let a1 = a / 2
        loop a1 (c+1)
    | _ -> (a,c)

// after staring at the result of the computation we came up with this theory:
let theory n = int (System.Math.Log10(float n) / System.Math.Log10(2.0))

[1..64] 
|> List.map (fun a -> a,loop a 0, theory a) 
|> List.map (fun (a0,(a,c),aa) -> a0,c,aa)

数据：

[(1, 0, 0); (2, 1, 1); (3, 1, 1); (4, 2, 2); (5, 2, 2); (6, 2, 2); (7, 2, 2); (8, 3, 3); (9, 3, 3); (10, 3, 3); (11, 3, 3); (12, 3, 3); (13, 3, 3); (14, 3, 3); (15, 3, 3); (16, 4, 4); (17, 4, 4); (18, 4, 4); (19, 4, 4); (20, 4, 4); (21, 4, 4); (22, 4, 4); (23, 4, 4); (24, 4, 4); (25, 4, 4); (26, 4, 4); (27, 4, 4); (28, 4, 4); (29, 4, 4); (30, 4, 4); (31, 4, 4); (32, 5, 5); (33, 5, 5); (34, 5, 5); (35, 5, 5); (36, 5, 5); (37, 5, 5); (38, 5, 5); (39, 5, 5); (40, 5, 5); (41, 5, 5); (42, 5, 5); (43, 5, 5); (44, 5, 5); (45, 5, 5); (46, 5, 5); (47, 5, 5); (48, 5, 5); (49, 5, 5); (50, 5, 5); (51, 5, 5); (52, 5, 5); (53, 5, 5); (54, 5, 5); (55, 5, 5); (56, 5, 5); (57, 5, 5); (58, 5, 5); (59, 5, 5); (60, 5, 5); (61, 5, 5); (62, 5, 5); (63, 5, 5); (64, 6, 6)]

Answer 3

递推关系为：

T(1) = a
T(n) = b + T(n/2)

第一部分来自循环变量等于 1 的情况，在这种情况下，只执行循环顶部的比较。第二行来自循环体 b 中完成的恒定工作量加上使用更新的循环变量值执行循环的时间。

前几项是：

n   T
1   a
2   a + b
4   a + 2b
8   a + 3b

据此我们可以猜出大概的形式：

T(n) = a + b log n

证明留作练习；但是你可以把它插入到递推关系中看看它是否满足要求。

渐近复杂度是对数的。

寻找递归关系和复杂性

Finding recurrence relation and complexity

c

complexity-theory

recurrence