somemo programming etc.

プログラマ、雑記、プログラミング関係はLinkから、数式はこっちでまとめていることが多い

なにを求めるのか

パターンと計算量

求めるもののパターンによって思考を変える

  • 入力に対して、単一の値を計算するだけ(スカラー値のみによる四則演算)
  • ある範囲(リストなど)から、単一の値を探し出す(search系)
  • など(具体例思いつかず…)

N>=1 としたとき

  • Nに関係なく決まる
  • 1回処理すると次の処理範囲が半減する
  • N回処理する
  • nestする
  • N回分岐する
  • すべての並べ方(順列)を試す

それぞれ

  • O(1)
  • O(logN)
  • O(N)
  • O(N2)
  • O(2N)
  • O(N!)

なにを出力(戻り値)するのか

  • スカラー
  • リスト
  • リストを要素に取るリスト

なにを入力(引数)するのか

出力と同じ

処理過程

  • 入力スカラー値からリストを作成することがある
  • 求めているものはスカラー値だけど、過程においてリストにためこみ、畳み込み->スカラー値にする

再帰とループ

  • パターンと計算量の最後の2つは、プログラムすると再帰になる傾向あり
  • O(N)の場合、再帰でも書けるけど、ループや畳込みでわかりやすく書いた方がいいことがある

どうやって一つにまとめるのか

  • リスト内のスカラー値に対して、2項演算の畳み込み
  • リストに要素を追加していく
  • リストを結合していく(リストのリスト、再帰停止条件で[[]] というものを返すときなど)
    • consで要素をつなげるパターン
    • リスト同士をつなげるパターン

まとめ

まとまらない