c++ - 算法的递归关系

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]);
   }
}

“推导上述算法的递归关系。假设基本情况是 T(1) = 正确。还假设交换函数在 O(1) 时间内交换它的两个参数的值，并且对于递归关系, T(n), 让 n = right-left+1."

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

Answer 1

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

调用 doSomething(arr, j, j) 打印 j 东西。
调用 doSomething(arr, i, j) 使 j-i 调用 doSomething(arr, i+1, j)。

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

调用 f(i) 使 i 调用 f(i-1)。

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

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

也就是说:

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

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