アルゴリズム論特論（塩田）第6回 (6) 法 $n$ の四則演算の計算量
前へ / 戻る / 次へ
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
$\newcommand{\binv}{\displaystyle{\frac{1}{b}}}$
法 $n$ の四則演算の計算量
Th.12 法 $n$ の四則演算の計算量は、加法、減法、乗法、除法いずれも $O(\log^2 n)$ である。
ただし引数・返り値は共に $0$ 以上 $n$ 未満の整数とし、除算の除数は法 $n$ と互いに素とする。
証明 加法、減法、乗法は、整数としての加法、減法、乗法に続いて $n$ による剰余計算を行うので $O(\log^2 n)$.
除算は拡張ユークリッドアルゴリズムと法 $n$ の乗法を組み合わせるので、やはり $O(\log^2 n)$ になる。(証明終)