使用FLOOR解算給定算法的遞推方程

您好，我完全失去了如何找到與給定算法相關的遞推方程。使用FLOOR解算給定算法的遞推方程

C(i, j, x) 
    if i=j then 
     if A[i] = x 
     return YES 
    else 
     return NO 
    else 
     if C(i, floor((i+j)/2), x) = YES 
      return YES 
     else 
      return C(floor((i+j)/2) + 1, j, x)

我得到的if語句，你只能算作1但我丟失如何讓遞推方程爲遞歸調用返回C（樓（（I + J）/ 2）+ 1，j，x）

MY結束嘗試將是t（n）= T（n/2 +1）+ 3; 任何幫助，將不勝感激。

謝謝。

來源

2014-10-02 user3221162

C使得兩個遞歸調用時，第一個返回NO，所以復發應該通過嘗試一些小例子

T(n) = T(ceiling(n/2)) + T(floor(n/2)) + 3.

在這裏，我摸索出T參數在右手邊。

C(1, 5, x) => C(1, 3, x) and C(4, 5, x) 
C(1, 6, x) => C(1, 3, x) and C(4, 6, x)

說實話，不過，如果你即將法師定理適用於像這樣的復發，那麼涉及地板和天花板的確切的說法並不重要。關於主定理的更一般的陳述Akra--Bazzi指出，在所有可能遇到的情況下，遞歸調用的參數中的一點模糊不會改變漸近分析。在這種情況下，具體而言，T是

T'(n) = T'(n/2) + T'(n/2) + 3.

來源

2014-10-02 03:37:27

這似乎是回答這個問題定義T'大-θ「是否數組包括x？」。它遞歸地搜索數組的下半部分，然後遞歸地搜索數組的上半部分，直到它找到X或檢查了所有的索引，並且可以說它不在數組中。所以它是T（n）= 2T（n/2）+ 3，它是由主定理O（n）。既然你必須在最壞的情況下檢查所有的指數來說'是'或'否'。

考慮這樣的情況，其中x是不數組中（我們將只使用A [1] = I與10個索引0到9的陣列）

x = 10 
i = 0, j = 9 
0. C(0, 9, 10) 
    i != j 
1. C(0,4,10) 
    i != j 
2. C(0,2,10) 
    i != j 
3. C(0,1,10) 
    i != j 
4. C(0,0) 
    i == j 
    A[i] != 10: Return NO. 
From 3. else: 
5. C(1,1, 10) 
    i == j 
    A[i] != 10: Return NO 
From 2. else: 
6. C(2,2,10) 
    i == j 
    A[i] != 10: Return NO 
From 1. else: 
7. C(3,4,10) 
    i != j 
8. C(3,3,10) 
    i == j 
    A[i] != 10: Return NO 
From 7. else: 
9. C(4,4,10) 
    i == j 
    A[i] != 10: Return NO 
From 0. else: 
10. C(5, 9, 10) 
    i != j  
11. C(5, 7, 10) 
    i != j 
12. C(5, 6, 10) 
    i != j 
13. C(5, 5, 10) 
    i == j 
    A[i] != 10: Return NO  
From 12. else: 
14. C(6, 6, 10) 
    i == j 
    A[i] != 10: Return NO  
From 11. else: 
15. C(6, 7, 10) 
     i != j 
16. C(6, 6, 10) 
    i == j   
    A[i] != 10: Return NO  
From 15. else: 
17. C(7, 7, 10) 
     i == j 
    A[i] != 10: Return NO  
From 10. else: 
18. C(8, 9, 10) 
    i != j 
19. C(8, 8, 10) 
     i == j 
    A[i] != 10: Return NO  
From 18. else: 
20. C(9, 9, 10) 
    i == j 
    A[i] != 10: Return NO  
10. Recieves No from all branches, returns No 
0. Recieves No from all branches, returns No.

哪個捲起導致20遞歸調用，你可以看到算法必須檢查每個索引，說'10不在數組中'。

來源

2014-10-02 03:48:23

使用FLOOR解算給定算法的遞推方程

回答

相關問題