为什么主定理不能适用

Question

做一个任务，并被困在了几个问题。

1. T（N）= T（2π/ 5）+ N
2. T（N）= T（2π/ 3）+ T（N/3）+ N
3. T（N）= T（n-2）+ n

有些东西告诉我他们所有的定理都不能应用。但为什么？他们的上限是什么（大哦）？

Answer 1

硕士定理可以应用到以下形式的任何复发

T（n）=在（N/B）+ O（N ^d）

其中a， b和d是常数。 （还有一些其他的表达方式，但是上面的一个处理更常见的情况）。具体而言，这意味着

• 问题大小必须由一个常数因子收缩，
• 子问题必须全部具有相同的尺寸，
• 必须有子问题的恒定数量，并
• 的加性项必须是一个多项式。

这些标准排除了第二次重复（次级问题没有相同的大小），第三次（问题大小必须缩小一个常数因子）。然而，第一次复发符合所有这四个标准。它可能有助于重写为

T（n）= T（n /（5/2））+ n。

在此基础上，你在什么情况下掌握了主定理，重复解决了什么问题？

Answer 2

主方法仅适用于以下类型的重复发生。

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1 

对于问题，

1. T（N）= T（2π/ 5）+ N

@templatetypedef已修改此递推方程，以适应主定理如

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

我想你可以从这里解决它。

2. T（N）= T（2π/ 3）+ T（N/3）+ N

显然，这不能直接由主定理解决。我们应该尝试构建递归树并查看。递归树形图的递归调用树和工作在每次调用完成的工作量。 以下是从here

所以拍摄的图像，这减少至O（N * log n）的

3. T（N）= T（N-2）+ N

显然这不能直接由主定理解决。 有一个为减法和征服类型派生的修改公式。

这个link可能是有用的。

对于形式的复发，

T(n) = aT(n-b) + f(n) 

where n > 1, a>0, b>0 

如果F（N）是O（n ^ķ）和k> = 0，则

1. 如果< 1则T（N ）= O（N ^ķ）
2. 如果= 1，则T（n）的= O（N ^{K + 1}）
3. 如果a> 1，则T（n）的= O（N ^ķ *一个^N/B）

我想你可以从这里解决。

希望它有帮助！