回溯算法时间复杂度问题

Question

void BackTrack(int t)
{
    //都装载了 
    if(t>n){
        //printf("%d\n",cw);
        if(cw > bestw)//当前车辆载重量>当前最优载重量
            {
            for(int i = 1; i <= n; i++)//遍历当前解
                {
                /*if(x[i])//若有装入 
                    bestx[i] = i;//放入当前最优解
                else*/
                    bestx[i]=x[i];//放入当前最优解
            }
            bestw = cw;//当前最优载重量=当前车辆载重量
            return;
        }
    }
        else
        {
        r -= w[t]; //更新剩余书重量
        if(cw + w[t] <= c1){ //没有超出载重量，判断是否可以向装载 当前车辆载重+当前书重量<=c1 
            x[t] = 1;
            cw += w[t];
            //printf("左:%d %d\n",t,bestw);
            BackTrack(t+1);
            cw -= w[t]; //cw要还原原先的载重，因为还要判断其他路线才能找到最优解
        }
        if(cw + r > bestw){ //判断是否可以向右(当前车辆载重量+剩余书重量>当前最优载重量)
            //printf("右:%d %d\n",t,bestw);
            x[t] = 0;
            BackTrack(t+1);
        }
        r += w[t]; //还原剩余书重量走其他路线(剩余书重量+=w[t])
    }
}

Answer 1

首先，这是个递归
递归里有两个分支，如果t>n，执行一个循环，循环次数为n
else，执行递归，t+1
那么其实就相当于双重for循环，内外层循环次数都是n
时间复杂度n^2