読者です 読者をやめる 読者になる 読者になる

第4回の備忘録

今回は色々と話題が出たので。
完全なメモです。

計算量の話

恥ずかしながら、O記法とΘ記法は若干異なるというのを知らなかった・・・
ω記法というものもあるらしい。

1.14

若干乱暴な議論をすると、コインの種類nが大きくなったら些細な差は無視していいよね。
なので、1セントの異なるコインがn種類あるとしたら、\theta(n^5)だよね、という話

脚注37

ちょっと混乱してきた。
n=5の時に必要な回数は3回であることから考える。
b^2 \dot b^2 \dot b = b^5

  • 2を底とするnの対数に、nの2進表現での1の数を足して1を引いたものは、
    • log_2 5 + 2(5の2進数表現の1の数の和) -1 = 2.3219... + 1 = 3.3219...
  • 2を底とするnの対数の2倍以下になる
    • 2 * log_2 5 = 2.3219 * 2 = 4.6438...

と脚注に書かれていた。この場合、確かになっていることを確認した。

1.19

行列の話として考えるといいという話
とりあえず問題とければいいやのノリでやっていたけど、変換行列をベクトル(a b)に掛け合わせていくという話に落としていく。

その他

面接でフィボナッチを出されたら、反復で解いたり、逐次平方の手順を使って対数ステップで解けるんですよ、的な話で面接官を混乱に陥れるといいですよ、という話になった。
素晴らしい。

次回の問題1.24まで