時間複雜度遞推關係

Question

我需要找到遞推關係：

int search(int[] a, int l, int h, int goal) { 
    if (low == high) return 0; 
    int tg = target(a, l, h); 
    if (goal < target) 
     return search(a, l, tg-1, goal); 
    else if (goal > target) 
     return search(a, tg +1, h, goal); 
    else 
     return a[tg]; 
} 

什麼是解決這個問題初始方法是什麼？我不是在尋求解決方案，而只是最初的方法。謝謝！

Answer 1

既然你不是在問一個確切的解決方案（但是，我可以提供，如果你想），我會給你一個提示，這是一個非常簡單，但不是一個衆所周知的接近方法這樣的問題。

的關鍵思路是修改功能，其中有可能是最糟糕的複雜的功能，但其預期複雜性很容易被衡量，我們稱之爲修正功能findTarget2：

public static int findTarget2 (int[] a, int low, int high, int goal) { 
    if (low == high) return 0; 
    int len = high - low + 1; //length of the array range, i.e. input size 
    while (true) { 
     int target = selectTarget(a, low, high); 
     if (goal < target && target-low <= 3/4 * len) 
      return findTarget2(a, low, target-1, goal); 
     else if (goal > target && high-target <= 3/4 * len) 
      return findTarget2(a, target+1, high, goal); 
     else if (goal == target) 
      return a[target]; 
    } 

} 

現在，讓我們f(n)是原始的時間複雜度，並且g(n)是findTarget2函數的時間複雜度，其中n是它們輸入的大小，即數組範圍的長度等於high-low+1。

現在，讓我們說，selectTarget導致錯誤的執行當且僅當它不會引起，而體內的任何回覆呼叫。

第一觀察是g(n) >= f(n)，因爲在錯誤的執行的情況下，基本上findTarget2調用自身上相同的輸入，而原來的功能降低了輸入的由至少1的尺寸。因此，如果有一個上限對於g(n)，則相同的限制適用於f(n)。

接着，g(n)預期時間複雜性可被寫爲如下：

EX[g(n)] <= EX[g(3/4 * n) + X * O(n)] 

其可以被寫爲如下使用線性期望值：

EX[g(n)] <= EX[g(3/4 * n)] + EX[X] * O(n) 

其中X是隨機變量表示while循環執行的次數，直到它返回調用，最後的O(n)是在findTarget2函數中花費的非遞歸時間，它是O(n)，因爲據說selectTarget函數在那個時候運行。

現在你的任務就是計算EX[X]，然後你可以使用Master theorem獲得的g(n)最終預期的時間複雜度，這也是一個上限的f(n)預期的時間複雜度，因此上界的複雜性原始功能。