時間の複雑さ - 不正な再帰 - 英国の変更の組み合わせ

Question

私は最近、英国の変更問題（すなわち、いくつのコインの組み合わせが所定の合計を生み出すことができるか）に対する素朴な（+貧弱な）解決策を思いついた。私は現在a better solutionを持っていますが、以下の2つのソリューションの時間と空間の複雑さを解決することには依然として興味がありました。

最悪のソリューション

このソリューションは、再帰的に重複した作業の多くで、その結果、自分自身に対するあらゆる数および他のすべての番号を組み合わせる試みます。私はそれがO（n^n）の時間であり、空間の複雑さをどのように測定するのかわからないと信じています（しかし、すべての結果を保存しているので、巨大です）。思考？

var makeChange = function(total){ // in pence 
    var allSets = new Set(); 
    var coins = [1,2,5,10,20,50,100,200]; 

    var subroutine = (arr, total) => { 
    if(total < 0){ return; } 
    if(total === 0){ 
     allSets.add(''+arr); 
    } else { 
     // increase each coin amount by one and decrease the recursive total by one 
     for(var i = 0; i<coins.length; i++){ 
     if((total - coins[i]) >= 0){ 
      subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i])) 
     } 
     } 
    } 
    }; 

    var zeros = new Array(coins.length).fill(0); 
    subroutine(zeros, total); 
    return allSets.size; 
}; 

の改善策

このソリューションは、まだ大規模なスペースの複雑さを持っていますが、私たちはコインの小さなサブセットにするたびに再帰しているので、時間計算量はO（N！）に-improved-を持っていると信じて。

var makeChange = function(total){ // in pence 
    var allSets = new Set(); 
    var coins = [1,2,5,10,20,50,100,200]; 

    var subroutine = (arr, total, start) => { 
    if(total < 0){ return; } 
    if(total === 0){ 
     console.log(''+arr); 
     allSets.add(''+arr); 
    } else { 
     // only solve for coins above start, since lower coins already solved 
     for(var i = start; i<coins.length; i++){ 
     if((total - coins[i]) >= 0){ 
      subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]), i); 
     } 
     } 
    } 
    }; 

    var zeros = new Array(coins.length).fill(0); 
    for(let i = 0; i<coins.length; i++){ 
    subroutine(zeros, total, i); 
    } 

    return allSets.size; 
}; 

私の時間/空間計算量の推定値が正しいか、そしてどのようにより良いこれらのような将来の問題を推定する場合は、私が理解するのに役立ちます。ありがとう！

Answer 1

最初のアルゴリズムの複雑さは実際にはO（n^n）ではありません。 Nはあなたの入力を表す変数です。この例では、変数 "total"を入力としているので、Nは合計に基づいています。あなたのアルゴリズムがO（n^n）であるためには、繰り返しツリーはNの深さとNの分岐係数を持つ必要があります。ここでは、繰り返しの深さはコイン配列の最小変数に基づいています。再帰ツリーのブランチが1つあり、毎回その値を減算し、合計がゼロになるまで再帰します。その値が一定であるとすれば、あなたの深さがnであると言うことは安全です。再帰ツリーのブランチングファクタは、コイン配列、またはその中の値の数に基づいています。関数呼び出しごとに、Cの関数呼び出しを生成します.Cはコイン配列のサイズです。つまり、あなたの関数は実際にはO（n^c）でなくO（n^n）であることを意味します。時間と空間の複雑さは、コイン配列のサイズと入力番号の両方に基づいています。

関数の空間の複雑さはO（n^c * c）です。関数を呼び出すたびに、入力に基づいてサイズの配列を渡します。すでにO（n^c）コールがあることを示し、各コールにはサイズcの配列が組み込まれています。

関数の複雑さを分析してすべての入力を考慮に入れるときは覚えておいてください。