平成15年秋期問3

質問

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

回答No.2

tekebon · ベストアンサー

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

参考URL：

http://edu.cs.inf.shizuoka.ac.jp/2005/X121/text/complexity.html

お礼

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

回答No.1

okg00

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

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

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

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

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

お礼

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