アルゴリズム論特論（塩田）2023年度

アルゴリズム論特論（塩田）第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)$ になる。(証明終)