令和３年度データベーススペシャリスト午前Ⅱ問１５

＜テーマ：入れ子ループ法における計算量＞

正解はこちら

解答：エ

[基礎知識・用語のまとめ]
[解法]
[参考]
利用させていただきました素材へのリンク

[基礎知識・用語のまとめ]

タプル・・・複数の構成要素からなる組を総称する一般概念であり、カタカナ語としては主に計算機科学において順序付けられた対象の並びを表すために用いられます。
n 個でできた組を英語で「n-tuple」と書くことに由来し、日本語に訳す場合、通常「n 組」とし、タプルの概念そのものも組と呼ばれます。

[解法]

タプル数nの表二つをそれぞれA、Bとします。入れ子ループ法による結合操作では、まず外側のループでAから１タプルを取り出し、次に内側のループでBのタプルを一つずつ取り出してAタプルとの比較を行います。つまり、Aの１タプルに対して、Bのｎタプルを比較し、これをＡのすべての（ｎ個）のタプルに対して繰り返します。

したがって、入れ子ループ法の計算量はｎ×ｎ=n²となって、O（n²）の選択肢「エ」が正解となります。