开发求和递归的动态规划算法

Question

我正在备考，教授给了我们一堆练习题，我们都没有答案。这是其中之一，但我一直在努力，甚至不知道我是否正朝着正确的方向前进。我什至不要求答案 - 只是有人为我指明正确的方向？

我应该为找到 expected number of acyclic orientations in a graph using this recurrence.

的以下函数开发动态编程算法（O(n^2)）

我想我应该使用主定理或展开求和来求解递归 simplify/solve 递归，然后从那里开发算法？任何提示或线索将不胜感激。谢谢！

Answer 1

当您提供了您需要的两个公式后，您可以通过以下步骤找到您需要的：

使用 O(n^2) 预计算 nCr（n 需要多大）
使用重复平方法预计算(1+x)^n（我想你知道x的定义域？所以它对所有n都是O(n lgn)
使用这些预先计算的值计算 A_n(X)，您最多有 O(n) 个子问题需要计算，每个子问题都使用 O(n) 得到 O(n^2)

已编辑：

对于第2点，就是对[0,n]中的i计算(1+x)^i(n-i)，虽然最大的幂可以达到n^2，但确实只有n 个实例，我们不需要计算直到 n^2 的所有幂。

让我们写下[0,n]中不同i的幂次序：0, n-1, 2(n-2), 3(n-3)...( n-1)(1)

我们可以用

这样的方式预先计算它们

function repeat_squaring(base, power){
  //O(lg (power))
}


for(int i=0; i<=n; i++){   
    repeat_squaring(1+x, i*(n-i));
}

那么现在，总共计算它们的复杂度是多少？总结一下吧！

T = O(lg n + lg(2n) + lg(3n) + ... lg(n*n)) = O(summation(lg(i)) + nlg(n)) = O(lg(n!) + nlgn) = O(n lg n)

对于O(lg(n!))的复杂度，有两种推导方式，一种是著名的斯特林近似，另一种是post：log(n!)

EDITED2：对于缩小 n 问题

我观察 (1+x)^(i(N-i)) 的模式 N = n, n-1, n-2..etc

您可以看到，我们可以从一些已经计算出的 (1+x)^(i(N-i))

中推导出更小 A_n() 的项 (1+x)^j

我们先用O(n lg n)预算出N = n的幂，也可以用O(n lg n)预算所有(1+x)^i的幂i in [0..n]

现在如图所示，术语 (1+x)^(i(N-i)) 表示连续的 N 值 (n vs n-1, n-1 vs n-2 ...)，您确实可以使用 O(1) 乘/除一些 (1+x)^i 其中 i in [0..n] （取决于您的实施，自下而上/自上而下）

所以我仍然认为你只需要O(n lgn)预先计算这些权力，并在需要时使用O(1)将它们动态地转换成其他权力。（你可以认为你同时对 (1+x)^(i(N-i)) 和 A_i() 进行动态规划）

TL;DR 当然，如果你不希望事情太复杂，你可以只使用 O(n^2) 在 (1+x)^(i(N-i)) 上为所有 N in [1..n]

做一个单独的 DP

// High Level Psuedo Code

var nCr[][]; 
var p[]; // (1+x)^0, (1+x)^1 ... (1+x)^n
var b[]; // (1+x)^0, (1+x)^(n-1),  (1+x)^2(n-2)...
var power[n][i] // (1+x)^i(n-i), power[max_n][x] = b[] actually
var A[] // main problem! 


Precompute nCr[][];  // O(n^2)
Precompute p[];  // O(n lg n)
Precompute b[]; // O(n lg n)

Precompute power[n][i] {
  // O(n^2)
  for all x, for all i
    power[x][i] = power[x+1][i]/p[i]
}

Compute A using all those precompute arrays, O(n^2)

开发求和递归的动态规划算法

Develop a Dynamic-Programming Algorithm for a Summation Recurrence

algorithm

recurrence

graph

dynamic