ニート歴10年からの数学日記

2008年〜2009年の高一の冬休みから無職。最長で4ヶ月ほどの中断アリ。

【随時更新】計算量の減らし方まとめ

追記:タイトルを「【随時更新】フローチャートの集合へのまとめ方」から「【随時更新】計算量の減らし方まとめ」に変更。


後日追記:線形走査法、つまり線的な走査にして、フローが散らばらないようにする工夫。複数ある変数の制約を1つの変数の制約にあつめる工夫。後ろだけを考えればその前は考えなくても全通りに対応できるような場合。エッシャーの絵のように、構成要素のそれぞれが対称になるようにして、1つだけ考えれば良いようにするという工夫。同じパターンでくり返す計算結果を予め出しておくという工夫。いろいろあって、それぞれ軽くなる理由も分かるけど、なにか体系的に説明できるものなのだろうか。博物学的なコレクションにしかならないような気もする。一応ページは残しておくが、その場合は、問題を記述して、後は計算量を減らすという方向性で良いかを確認するという研究になるだろう。
 

原理的に発散するフローチャートを集合にまとめる

  • 単にまとめる
  • 数としてまとめる
  • ルールとしてまとめる(直線状あるいは分岐において)
  • 倍数としてまとめる
  • 違う2つを共通項でまとめる
  • スタート・ステップ・ゴールとして明確化する(更に明確化したものの中で制約を見出す)

 

全体を利用する

  • 単にまとめる
  • 全体の中の否定で肯定部分を浮かび上がらせる
  • 全体からはみ出した部分に着目する
  • 一番大きな制約から取りかかる
  • 組み合わせにおいて出現数が0か全部だったら、それについては一通りに定まる
  • 数列において全体にギッシリ詰まっていると移動だけで一定数かかる、つまり違う問題になる