【デスペ4問】計算量の「大まかな数」（データベーススペシャリスト試験）
基本情報技術者試験で、2分探索の計算量の問題とか出ましたよね。
デスペでも計算量の概算が出るので、まとめておきました。毎回1～2問出題されます。
仕組みはともかく、答えさえ覚えて正解しさえばOK。午後問題では出ないので、AMIIでお別れですから。
入れ子ループ法：n^2
B＋木インデックス：log X
射影の数：2^n
これだけ覚えておくだけ。
デスペのAMIIはざっくり5年分解けば、全パターンが把握できます。
私が合格した時に、学習ノートにジャンル毎に問題をまとめました。このNoteの解説は、学習ノートと、私のIT専門学校での授業内容を基にしています。
それでは始めましょう！
入れ子ループの計算量
ここからは、厳密な計算ではありません。オーダーとは大体の数、増減の大まかな様相です。「大体こんな数になる」「大体こんな増減をする」という見積もりです。
関係データベースにおいて、タプル数nの2つの表を結合を、入れ子ループ法で実行したときの計算量の大まかな評価値（オーダー）はどれか
ア：2n
イ：log n （底は10）
ウ：n^2 （nの2乗）
エ：n log n （底は10）
正答はウ。
入れ子ループ法とは、2表を結合する時に、一方の表を1行ずつ読み込み、もう1つの表の全行と比較して結合する手法です。
例えば、片方の表がn行、もう片方もn行とすれば、n×n = n^2回になります。仮に、n行とm行でもn×mの形ですから、選択肢ではn^2が一番近い形ですね。
最近は少し選択肢が変わっています。
O(～)は、値の変化を大雑把に算出する記号です。例えば2nや3nを、nに比例するのは同じなのをO(n)と表せます。
関係データベースにおいて、タプル数nの2つの表を結合を、入れ子ループ法で実行したときの計算量はどれか
ア：O(log n) ※底は10
イ：O(n)
ウ：O(n log n) ※底は10
エ：O(n^2) ※底は10
平成29年午前2問19より改変
平成31年午前2問16より改変
令和03年午前2問15より改変
正答はエ。
B＋木インデックスのアクセス回数
B+木インデックスによる候補キーを使って、1件のデータを検索するとき、データ総件数Xに対するアクセス回数のオーダーはどれか
ア：Xの平方根
イ：log X
ウ：X
エ：X!
正答はイ。答えを覚えれば良いです。
一応簡単な解説にしますが、読まなくて大丈夫です。
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の様相になります。
詳しい解説は、過去問道場さんをどうぞ。
射影の個数
属性がn個ある関係の異なる射影はいくつか。なお、射影の個数には、元の関係と同じ結果となる射影、属性を全く含まない射影の2つを含める。
ア：2n
イ：2^n（2のn乗）
ウ：log_2 n （底は2）
エ：n
平成29年午前2問13より改変
平成31年午前2問13より改変
令和03年午前2問09より改変
正答はイ。
射影とは、データベースの属性（列）を抜き出すことです。
例えば、データベースに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就職のブログ << をやってます。
でわでわ（・ω・▼）ノシ
