algorithm - 動的計画法を使用しないアルゴリズム、効率の悪いソリューション

Question

コンテストで出題される問題があります。私はすでに動的計画法とその複雑さでこの問題を解決しましたO(n^2)。しかし、効率の悪い方法で解決策を探しています。この効率の悪い方法の複雑さはどうなるでしょうか。助けてくれてありがとう。

Answer 1

動的計画法ソリューションの効率を下げる一般的な方法があります。動的計画法の本質は、サブ問題の解を再利用のために保存することです。

合理的な方法で効率を下げるには、サブ問題の結果ストレージを取り除きます。代わりに、必要なときにいつでもサブ問題の各ソリューションを再計算してください。

Answer 2

同じアルゴリズムで非効率的なデータ構造を使用すると、O(n^3). 町を配列ではなく連結リストに格納すると、アルゴリズムの効率が 1 桁低下します。

さらに効率を下げるために、アルゴリズムを変更する方が簡単です。たとえば、すべてのハービンジャーの変化する組み合わせをチェックし、最小値を使用します。これは時間の指数関数的です。