まとめ

• 自然数 $n$ のビット長は $O(\log n)$.
• $n$ 以下の自然数の四則演算の計算量は、加法・減法は $O(\log n)$, 乗法・除法は $O(\log^2 n)$.
• $\log$ の関数値は極めて小さい。
• 計算量が $\log$ で書けているアルゴリズムは速い。

自宅学習の例

• operations.py を実行して、加減乗除の計算時間を体感してみる。