algorithm - 自顶向下动态规划算法的运行时间

Question

我为一项任务提出了以下算法。主要是第 23-24 行中的 for 循环让我不确定。

function TOP-DOWN-N(C, n, p)
  let N[1...n, 1...C] be a new array initialized to -1 for all indicies
  return N(C, n)

function N(C, n)
  if N[C,n] >= 0 then
    return N[C,n]
  if C < 0 or n < 1 then
    return 0
  elif C = 0 then
    return 1
  elif C > 0 and i > 0 then
    r = 0
    for i = 0 to n do
      r += N(C-p[n-i], n-(i+1))
    N[C,n] = r
    return N

标签： algorithmtimetime-complexitydynamic-programming

Answer 1

让我们忽略这个算法是递归实现的事实。一般来说，如果动态规划算法正在构建一个包含 N 个结果的数组，并且计算每个结果需要使用来自该数组的 k 个其他结果的值，则其时间复杂度为 Ω(Nk)，其中 Ω 表示下限。这应该很清楚：使用 k 值来计算结果需要 Ω(k) 时间，并且您必须这样做 N 次。

另一方面，如果计算不做任何渐近比从数组中读取 k 值更耗时的事情，那么 O(Nk) 也是一个上限，因此时间复杂度为 Θ(Nk)。

---

所以，按照这个逻辑，我们应该期望你的算法的时间复杂度是 Θ(n ² C)，因为它构建了一个大小为 nC 的数组，计算每个结果使用来自该数组的 Θ(n) 其他结果，并且计算是不被别的东西支配。

但是，您的算法比迭代实现具有优势，因为它不必计算数组中的每个结果。例如，如果数字 1 不在数组中，p那么您的算法将不会计算N(C-1, n')任何n'; 如果 in 中的数字p都大于或等于 C，则循环只执行一次，运行时间主要取决于必须初始化大小为 nC 的数组。

由此可知 Θ(n ² C) 是最坏情况下的时间复杂度，最好情况下的时间复杂度是 Θ(nC)。