応用情報技術者 試験情報＆徹底解説

解答がオ：O(1)、カ：O(n)となる理由がわからないので教えてください

https://www.ap-siken.com/kakomon/26_haru/pm03.html

よろしくお願いします

空欄オは「空間計算量」、空欄カは「時間計算量」を問われています。
空間計算量は、処理を達成するために必要なメモリ空間の容量
時間計算量は、処理を達成するために必要な時間
を表します。それぞれ、アルゴリズムの空間的、または時間的な量をある程度見積もるための指標です。

[空欄オ]
本文中に
>循環節を検出する方法では，割り算の各桁で現れる余りの種類の最大である n－1 種類の余りを記録する必要がある。その配列の大きさは n に比例することになり，処理できる n の値は使用可能な記憶域の大きさによって制約される。
とあります。
この文章のみを見ると、必要な空間計算量は配列の要素数「n」に比例するためO(n)と答えたくなりますが、その直後に
>記憶域の制約を受けない，"ウサギとカメ"に例えられるフロイドの循環検出法のアルゴリズムを用いる。
とあります。これは、前述の考え方とは違い、計算の途中に必要な記憶域に配列を利用しません。図６を見ても、配列は登場していません。
したがって、O(1)となります。

[空欄カ]
問題文の冒頭の文章を読むと、計算が行われる回数（桁数）の話が出てきます。
最終的なオチとして
>循環節の桁数は最大 n－1 である。
と述べられています。
そのため、時間（回数）的には n-1 回の計算がなされるわけです。
したがって、O(n)となります。

空間計算量は必要な最大容量
時間計算量は最大回数(桁数)
を元に考えれば良いんですね。

ありがとうございます。