アルゴリズム論特論(塩田) 2017年度教材 第1回
授業内容
慣用記号
自然数 n のビット長 = O(log n)
2進数の計算問題
exercise01.pdf
をやってみよう。
Wikipedia で
加算器の構造
を見てみよう。
四則演算の計算時間を計測する Python プログラム
operations.py
ツボ
y = log x のグラフの真の姿
log の関数値は極めて小さい
n 以下の2つの正整数の四則演算の計算量は
加法, 減法: O(log n)
乗法, 除法: O(log
2
n)
戻る