基本情報 １４年秋期午後問(2)について

質問

こんにちは、２０１０年１０月の基本情報技術者試験を受験して
午後試験で　５０．５０点だったものです。

趣味でプログラミングをしていて、

JavaScriptでポーカーを再現し、

同じくJavaScriptで音声は出ませんが、

http://sdin.jp/browser/casino/blackjack/

と同様の動作をするブラックジャックを作るくらいです。
( CGI, サーバーのことはよくわかりません。)

現在　暇な時間をみて、４月の同試験の受験に向けて勉強しているのですが、
わからないことが出てきましたので、質問させていただきます。

以下のサイトをコピペして、みていただきたいのですが・・・

http://情報処理試験.jp/FE14b-pm/t02.html

(1)「問２の設問２は、リストの要素のポインタの値を変えるだけなので、
　　そのオーダは、テキストの文章の行数に関係なく[定数]である。」

(2)「設問１は、二重ループである挿入ソートの値をずらしていく部分と
　　同様な処理なので、一重のループであり、オーダは [ｎ] である。
　　よって、行数やCPの値でオーダは変化する。」

(1)、(2)のような解釈でよいのでしょうか。

もし間違っていたら、どなたか、教えていただけないでしょうか。
よろしくお願いします。

回答No.1

jjon-com · ベストアンサー

(1)
正しいです。
「定数である」と言葉を濁す必要はなく「オーダは１である」です。
DELETE()，GET()，INSERT(x) のいずれも，変数CP の位置から即座に処理できますから。

LAST() だけはこれに該当しません。最後の行の内容はTAILから即座に特定できますが，全行数については，HEADからTAILまであるいはTAILからHEADまで順にポインタをたどりつつカウントしなければ分かりません。よって，行数をｎで表すなら，その計算量は「ｎのオーダ」です。

(2)
前２行は正しいです。最後の「行数やCPの値でオーダは変化する」は間違いです。
ｎ＝100のとき，ｎ＝1000のとき，ｎ＝10000のとき，それぞれのループ回数は異なります。CPの値によってもループ回数は異なります。
それを踏まえて計算量（オーダ）とは「これらの変化はまとめてどんな式で表現できるか（何に比例して増えているのか）」を表す関係式です。個々の値を当てはめた場合の計算回数は変化しますが，オーダは変化しません。

お礼

いつも回答していただきありがとうございます。
教えていただいた通り、
「繰り返し回数」は変化しても
「オーダ」は変化しないプログラムということなのですね。
いつも自分ではあやふやなところを指摘していただき、
ありがとうございます。
貴重な時間をさいての回答、ありがとうございました。