アルゴリズムの簡単なまとめ Wiki - yukicoder

アルゴリズムの簡単なまとめ 運営者が昔、メモ程度にどこかに書いてたものです。間違っている箇所がありましたら教えて下さい。 順次追加・修正中(ページごとに分けてもいいし、良いページができたら削除したい) 計算手段 再帰呼び出し 自分自身の関数を呼び出すこと、forやwhileのループでもできることが、再帰呼び出しのほうが記述しやすいこともある。 末尾再帰 return に再帰関数を呼び出すこと、return以外に再帰呼び出しがないこと 注意としては再帰の結果をすぐにreturnすること(再帰の結果を更に演算したりなどはNGのはず） 動き的には末尾の再帰のreturnをすると、それ以降returnの処理しかないような動き。 これをする理由は、（言語によってはしてくれない）末尾呼び出し最適化が働き、スタックを定数量しか消費しないようにしてくれる。 数学的アルゴリズム 最大公約数 (GCD) ユー

[sattomi]

“巡回セールスマン問題(TSP) 辺にコストが有り、すべての頂点を１回だけ通り、始点に帰ってくる経路（つまり閉路）の最短経路問題 辺のコストが1または無限大（通れない）の条件がつくとハミルトン閉路 NP困難 DPでO(2nn2)