【デスペ4問】計算量の「大まかな数」（データベーススペシャリスト試験）

基本情報技術者試験で、2分探索の計算量の問題とか出ましたよね。

デスペでも計算量の概算が出るので、まとめておきました。毎回1～2問出題されます。

仕組みはともかく、答えさえ覚えて正解しさえばOK。午後問題では出ないので、AMIIでお別れですから。

• 入れ子ループ法：n^2

• B＋木インデックス：log X

• 射影の数：2^n

これだけ覚えておくだけ。

デスペのAMIIはざっくり5年分解けば、全パターンが把握できます。

私が合格した時に、学習ノートにジャンル毎に問題をまとめました。このNoteの解説は、学習ノートと、私のIT専門学校での授業内容を基にしています。

それでは始めましょう！

入れ子ループの計算量

ここからは、厳密な計算ではありません。オーダーとは大体の数、増減の大まかな様相です。「大体こんな数になる」「大体こんな増減をする」という見積もりです。

正答はウ。

入れ子ループ法とは、2表を結合する時に、一方の表を1行ずつ読み込み、もう1つの表の全行と比較して結合する手法です。

例えば、片方の表がn行、もう片方もn行とすれば、n×n = n^2回になります。仮に、n行とm行でもn×mの形ですから、選択肢ではn^2が一番近い形ですね。

最近は少し選択肢が変わっています。

O(～)は、値の変化を大雑把に算出する記号です。例えば2nや3nを、nに比例するのは同じなのをO(n)と表せます。

正答はエ。

B＋木インデックスのアクセス回数

正答はイ。答えを覚えれば良いです。

一応簡単な解説にしますが、読まなくて大丈夫です。

B+木は、全ての枝の深さが同じ木です。

• 検索すべき葉の個数をXし

• 根から枝がb個に分かれている（次数b）とき

• 根から葉までの深さをhとすれば

X = b^h　が葉の個数です。

例えば、枝分けれが2（次数b=2）、枝の深さが3（h=3）の時、葉の個数X = 2^3 = 8個です。

B+木インデックスは、2分探索木のように左右と階層の大小関係が整理された木で、データと一緒にポインタも記録されています。

探索したい値まで枝をシンプルに辿るので、どの値でも探索回数がほぼ同じで、枝の深さに比例します。

したがって、X=b^hから、枝の深さh = log_b X。

アクセス回数はlog Xの様相になります。

詳しい解説は、過去問道場さんをどうぞ。

射影の個数

正答はイ。

射影とは、データベースの属性（列）を抜き出すことです。

例えば、データベースに2つの列（A, B列）があれば、射影はAだけ・Bだけ・AとBだけ・AもBもないの4通り。「AもBもない」は、問題文の「属性を全く含まない射影」に当たるので数えます。不思議ですね。

もし3つの列（A, B, C列）あれば、8通り。

• 0列

• 1列：A、B、C

• 2列：AB, AC, BC

• 3列：ABC

以上2つの例から、射影の数は2^nだと分かります。

まとめ

お疲れ様でした！

オーダーとは大体の数、増減の大まかな様相。

• 入れ子ループ法：n^2

• B＋木インデックス：log X

• 射影の数：2^n

これだけ覚えておくだけで良いと分かりましたよね。

私が合格してきた勉強法についてもNoteにしました。

まずは書籍の読み倒し方、AMIIの勉強だけでも参考にして頂ければ、嬉しいです。

p.s. 普段は >> 専門学校とIT就職のブログ << をやってます。

でわでわ（・ω・▼）ノシ