再帰組み合わせ時複雑分析

Question

int C(int n, int k){ 
    if(n==k || k==0)return 1; 
    return C(n-1, k) + C(n-1, k-1); 
} 

Answer 1

がT(a,b)がC(a,b)C(n,k)の再帰コールツリーに呼び出される動作時間の数とするT（n）の中の再帰二項係数の指数関数的な時間計算のための任意の説明。 C(a,b)はC(a+1,b)とC(a+1,b+1)の両方から呼び出されます（これらの2つのいずれかが呼び出されるたびに）T(a,b)=T(a+1,b)+T(a+1,b+1)となります。これはPascal's triangle formulaある：再帰コールツリーの最後のレベルでT Sはパスカルの三角形のn番目レベルを形成し、従ってnは（例えばk=n/2ために、エッジケース例えばk=1又はk=nを禁止する。）を用いて指数関数です。

cache the resultsの場合、アルゴリズムはO(n*k)時間にすることができます。