寻找指数算法的时间复杂度。

Question

问题：寻找最佳的方法来切割一根长度的棒子。n.每个切口都是整数长度.假设每个长度为 i 棒子有价 p(i).给定：杆长 n以及价格清单 p的价格，它提供了0和0之间每个可能的整数长度的价格。n

可以使用任何数量的切口，从0到1，以获得最大的价格。n-1.没有成本的切割。

下面我提出一个天真的算法来解决这个问题。

CUT-ROD(p,n)
if(n == 0)
    return 0
q = -infinity
for i = 1 to n
    q = max(q, p[i]+CUT-ROD(p,n-1))
return q

如何证明这个算法是指数型的？Step-by-step.I can see that it is exponential. 但是，我无法证明它。

Answer 1

为了清晰起见，我们把代码翻译成C++。

int prices[n];
int cut-rod(int n) {
  if(n == 0) {
    return 0;
  }
  q = -1;
  res = cut-rod(n-1);
  for(int i = 0; i < n; i++) {
    q = max(q, prices[i] + res);
  }
  return q;
}

注意： 我们正在缓存结果 of cut-rod(n-1) 以避免不必要地增加算法的复杂性。在这里，我们可以看到 cut-rod(n) 电话 cut-rod(n-1)，这就要求 cut-rod(n-2) 诸如此类 cut-rod(0). 对于 cut-rod(n)，我们看到函数在数组上迭代的是 n 次。因此该算法的时间复杂度等于 O(n + (n-1) + (n-2) + (n-3)...1) = O(n(n+1)/2) 约等于 O((n^2)/2).

EDIT.如果我们使用与问题中完全相同的算法，其时间复杂度为O(n!)，因为cut-rod(n-1)调用cut-rod(n-1)n次。如果我们使用与问题中的算法完全相同的算法，它的时间复杂度是O(n!)，因为cut-rod(n)调用cut-rod(n-1)n次。 cut-rod(n-1)调用cut-rod(n-2)n-1次，以此类推。因此时间复杂度等于O(n*(n-1)*(n-2)...1)=O(n!)。