递归关系练习集

2024-04-23 06:55:03 326

递归关系是递归定义多维数组的方程式。

在这里，我们将基于递归关系解决问题。

Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2.
T(n) = 12T(n/2) + 9n2 + 2.
Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2
It is of the form f(n) = O(n^c), where c = 2

这是在硕士定理条件下形成的

So,
logb(a) = log2(12) = 3.58
Using case 1 of the masters theorm, T(n) = θ(n3.58).

Solve the recurrence reation:T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3.
T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3

为简化起见，在较大值的情况下，n，n/2>>23，因此忽略23。

T(n) = 5T(n/2) + 5n2 + 7n - 5/3.
Further, we can take 5n2 + 7n - 5 ≃0(n2).
So, T(n) = 5T(n/2) + O(n2)

这属于大师定理的情况2，

So, T(n) = O(n2).

检查以下情况是否属于硕士定理。

T(n) = 2T(n/3) + 5n

否，要应用大师定理，该函数应该是多项式函数。

T(n) = 2T(n/5) + tan(n)

不，三角函数不属于大师定理。

T(n) = 5T(n+1) + log(n)

不，对数函数不属于大师定理。

T(n) = T(n-7) + en

不，指数函数不属于大师定理。

T(n) = 9n(n/2+1 ) + 4(n2) - 17
Yes, as solved above.

递归关系练习集

热门推荐

随机推荐