时间复杂度递推关系

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)预期的时间复杂度，因此上界的复杂性原始功能。