アルゴリズム論特論(塩田)第1回 (4) 今日のまとめ

まとめ

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

自宅学習の例

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