如何计算回溯的空间复杂度？

Question

对于回溯算法，计算空间（堆栈空间）和时间复杂度的好方法是什么？

我们希望输出组合的长度正好是K，并且sol集必须是唯一的

输入：arr:[1,2,3,4,5]k:4

输出：

[1,2,3,4]//[2,1,3,4]无效,因为它==[1,2,3,4]

// arr == [1,2,3,4,5]
// K   == 4
// backtrack(arr,4,0,{},...other params we don't care)

void backtrack(vector<int> &arr, int K, int start, vector<int> &sol, ...)
{
     if(sol.size() == K)
     {
         //...
     }
     else
     {
           for(int i = start; i < arr.size(); i++)
           {
              sol.push_back(arr[i]);
              backtrack(arr, K, i+1,sol,...);
              sol.pop_back();
           }
     }
}

                   []
      f1()    f2() f3() f4() f()5  
f1.1() f()1.2 ... 

最差的时间复杂度是O(n^k)，其中n是数组的长度。

Answer 1

从技术上讲，时间复杂度不是O(n^k)，而是类似于O（sum from i=1 to k bin（n,i））的，因为您不是从arr的开始搜索，而是从解的最后一个元素之后的元素开始搜索，也不像[3]那样切掉无法完成的状态。通常，在这种情况下，时间复杂度是状态数乘以从一个状态到另一个状态所需的平均时间。