时间复杂度递归关系

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 导致 执行错误 当且仅当它不会在 while 的主体内引起任何 return 调用.

第一个观察是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 循环执行次数的随机变量，直到它导致 return 调用，最后一个 O(n) 是在 findTarget2函数，而它是O(n)，因为据说selectTarget函数在那段时间运行。

现在你的任务只是计算EX[X]然后你可以使用Master theorem得到最终的预期时间复杂度g(n)，这也是预期的上限f(n)的时间复杂度，所以原函数复杂度的上界。

时间复杂度递归关系

Time complexity recurrence relation

algorithm

recurrence

time-complexity