H26春  午後  問3  設問4

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

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

よろしくお願いします

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

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

[空欄カ]
問題文の冒頭の文章を読むと、計算が行われる回数(桁数)の話が出てきます。
最終的なオチとして
>循環節の桁数は最大 n-1 である。
と述べられています。
そのため、時間(回数)的には n-1 回の計算がなされるわけです。
したがって、O(n)となります。
2019.10.16 09:45
へりさん  
(No.3)
空間計算量は必要な最大容量
時間計算量は最大回数(桁数)
を元に考えれば良いんですね。

ありがとうございます。
2019.10.16 21:17

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop