爲什麼主定理不能適用

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）

我想你可以從這裏解決。

希望它有幫助！