第４回の備忘録
今回は色々と話題が出たので。
完全なメモです。
計算量の話
- Oは上限だけを抑えている（最大の計算量のみを抑えている）
- Θは上限と下限を抑えている
- ランダウの記号 - Wikipedia
- 計算量 - Security Akademeia
恥ずかしながら、O記法とΘ記法は若干異なるというのを知らなかった・・・
ω記法というものもあるらしい。
1.14
若干乱暴な議論をすると、コインの種類nが大きくなったら些細な差は無視していいよね。
なので、1セントの異なるコインがn種類あるとしたら、だよね、という話
脚注37
ちょっと混乱してきた。
n=5の時に必要な回数は3回であることから考える。
- 2を底とするnの対数に、nの2進表現での1の数を足して1を引いたものは、
+ 2(5の2進数表現の1の数の和) -1 = 2.3219... + 1 = 3.3219...
- 2を底とするnの対数の2倍以下になる
- 2 *
- 2 *
と脚注に書かれていた。この場合、確かになっていることを確認した。
1.19
行列の話として考えるといいという話
とりあえず問題とければいいやのノリでやっていたけど、変換行列をベクトル(a b)に掛け合わせていくという話に落としていく。
