算法的递归关系

Question

void doSomething(int *a, int left, int right){
   if (left == right){
      for (int j = 0; i < right; ++j)
         cout << a[j];
      cout << endl;
      return;
   }
   for (int i = left; i < right; ++i){
      std::swap(a[left], a[i]);
      doSomething(a, left + 1, right);
      std::swap(a[left], a[i]);
   }
}

"Derive the recurrence relation for the above algorithm. Assume that the base case is T(1) = right. Also assume that the swap function exchanges the values of its two arguments in O(1) time and for the recurrence relation, T(n), let n = right-left+1."

我们被要求找出上面给出的代码的递推关系。我们能够得出结论，第一个 'if' 语句只是在 left == right 时打印出数组的内容。最下面是一个递归语句，但是我们不知道如何分析它的复杂度。如有任何帮助，我们将不胜感激！

Answer 1

与swap无关。它会影响打印的内容，但不会影响算法的运行时间。那么让我们看看会发生什么：

调用 doSomething(arr, j, j) 打印 j 东西。
调用 doSomething(arr, i, j) 对 doSomething(arr, i+1, j) 进行了 j-i 次调用。

让我们稍微重新定义变量，将f(i)定义为doSomething(arr, j-i, j)。这样 f(0) 就是基本情况。现在递归规则可以重写为：

调用 f(i) 对 f(i-1) 进行了 i 次调用。

这使得递归关系非常清楚：

T(n) = n * T(n-1)
T(1) = O(n)

也就是说：

T(n) = O(n! * n)

不用说，这是一个相当大的运行时间！

算法的递归关系

Recurrence relation of an algorithm

c++

algorithm

recursion

recurrence