数学のブログ

整数約数と倍数 2つの正整数の積、最大公約数と最小公倍数の積

親切な代数学演習新装2版―整数・群・環・体
 楽天ブックス
Yahoo!
au PAY マーケット

学習環境

親切な代数学演習新装2版―整数・群・環・体 (加藤明史(著)、現代数学社)の第Ⅰ部(整数)、第1章(約数と倍数)の問7の解答を求めてみる。

2.1

\begin{array}{l} T_{1} (N) = O (N) \\ T_{2} (N) = O (N^{2}) \\ T_{3} (N) = O (N^{2}) \\ T_{4} (N) = O (N^{\frac{3}{2}}) \\ T_{5} (N) = O (2^{N}) \end{array}

2.2

0 \leq i < j < k < N

よって、

(\begin{matrix} N \\ 3 \end{matrix}) = \frac{N!}{(N - 3)! 3!} = \frac{N (N - 1) (N - 2)}{3!}

ゆえに求める計算量をラウダウの記法を用いて表したものは、

O (N^{3})