背景
人生で何度目かのアルゴリズムのお勉強を開始しました。
いつも計算量のところで意味がわからなくて「私には無理じゃ」と放り出してしまうのですが、今回は社内勉強会という素晴らしい場と仲間と共にやっていけることになったので、やる気が高まっています。 勉強会自体は題材はこの本、事前に1章読んできて、勉強会では章末問題を解くスタイルです。 www.kspub.co.jp 1周で理解できると到底思えなかったので私としては「章末問題はスキップして自分で1周読み切ろう。勉強会で2周目を回して、章末問題で理解度と実践度を測っていくようにしよう*1」と考えて読み始めたのがこの記事を書いている今のステータスです。
"上から抑える"
2章を読んでいます。この章のテーマは計算量です。その中に「上から抑えることができるのでこれは多項式時間です」と言う旨の文章があり「”上から抑える”とは？？？権力持った何かが下界の者を締め付ける的な？そもそも”上”って何」となって全く意味がわからなかったので調べてみました。調べてみたら単純な話でした。
参考にしたサイト: 整数問題〜不等式を使う問題〜 | 大学受験のための高校数学
例えば
x, y, zをx < y < z をみたす自然数とするとき、x + y + zは次のように挟むことができます。
x + x + x < x + y + z < z + z + z ⟺ 3x < x + y + z < 3 z
3x < x + y + z のようにすることを下から押さえる、
x + y + z < 3z のようにすることを上から押さえるといいます。
（サイトを見ると自然数の場合、という条件付きなのがやや気になっていますが）範囲を指定することを「押さえる」と言うのだなとわかりました。
漢字が「抑える」なのか「押さえる」なのかは問題じゃないのかが引っかかりましたがここでは置いておきます。
このように（上から|下から）抑えておくと、探索範囲が絞られるので、処理が少なくすみます。
最後に
意味としてはシンプルでしたが、こういう用語があるとわかっていなかったので勉強になりました。技術書・専門書を読むときにいちいち止まると時間がかかる、時間がかかりすぎると読み進めるのが苦行になってしまうというのが自分にとっては注意点なのですが、数学的な用語については曖昧にせずに逐一理解していこうと思いました。
*1:今が5/5で勉強会が始まるのが5/13なので1周できると信じています
