HOME»応用情報技術者試験掲示板»アルゴリズムの計算量
投稿する

[1537] アルゴリズムの計算量

 T.S.さん(No.1) 
H26年春期の午後のプログラミングについて、「循環節の桁数は最大n-1」とあるのですが、
空欄オはO(n)にならないのはなぜでしょうか?

よろしくお願いいたします。
URL:https://www.ap-siken.com/kakomon/26_haru/pm03.html
2019.04.02 21:29
助け人さん(No.2) 
AP ゴールドマイスター
〔循環節を検出するアルゴリズム〕に、
「単純に余りを配列に記録して,・・・その配列の大きさは n に比例することになり,
処理できる n の値は使用可能な記憶域の大きさによって制約される。そこで記憶域の制約を受けない,"ウサギとカメ"に例えられるフロイドの循環検出法のアルゴリズムを用いる。」
とあることから、また、図6のプログラムを見てもnに依存する配列などは定義されていないことから、O(1)です。
2019.04.02 21:57
 T.S.さん(No.3) 
ご回答ありがとうございます。
記憶域のO記法は計算量とは違って、
配列を使わないプログラムにはO(1)になるということですね。
2019.04.03 12:18

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop