平成15年秋期問3

平成15年秋期問3のbについて
4kn+2kが実行時間となる場合、オーダがnになる仕組みがわかりません。
ご理解のある方は教えて頂けませんか?

No.2 ベストアンサー 回答者： tekebon 回答日時： 2006/10/13 16:53

下の方の書かれた問題として回答します。

オーダは「おおざっぱに」データ数の増加に対してどのくらいの
計算量の増加があるかということを表します。
（一般的にBig-O記法というものを使います）
たとえば「10n+3」という計算量がありnが十分大きな数字と
なったとします。すると3だけ増えようが誤差の範囲と
考えることができます。よってnに対して最も次数の高いもの
（この場合は4knの項）以外は無視します。
また、データ数に対する計算量なので係数も無視します。
よって4kn+2kの処理に対するオーダはnと考えます。
下記に参考URLを載せておきます。

参考URL：http://edu.cs.inf.shizuoka.ac.jp/2005/X121/text/ …

この回答へのお礼

お返事ありがとうございます。
ご説明とリンク先のお話がとても理解しやすかったです。
ありがとうございます。

お礼日時：2006/10/17 14:00

No.1 回答者： okg00 回答日時： 2006/10/13 15:49

科目・午前か午後かが解らないと答えようがありません。

問題文はどこかにないですか？


仮に基本情報の午後だとして
http://www.rs.kagu.tus.ac.jp/infoserv/j-siken/H1 …

kは一定値(つまり定数と見ることができる)だから、nを変化させた場合のオーダはnになる。

何が納得できないのですか？

この回答へのお礼

お返事ありがとうございます。
科目・午前午後の指定をしていなくてご迷惑をおかけしました。
リンクどおりのものです。
オーダそのものの定義についての理解が足りなかったようです。

お礼日時：2006/10/17 13:59