平成28年度秋期 応用情報技術者試験 午前 問27

正解：イ

AI解説

正解はイのlogX。B+木インデックスは多分岐の平衡木(バランス木)であり、根から葉までの深さはデータ件数Xに対して対数的にしか増えない。1件の検索では根から葉へ1経路をたどるだけなので、アクセス回数のオーダはO(logX)である。件数が増えてもアクセス回数はゆるやかにしか増えないことがB+木の利点である。 ア: 誤り。√Xのオーダになる代表例はブロック分割探索などであり、木構造の探索ではない。 イ: 正解。B+木は平衡木で木の高さがlogXに比例するため、検索時のノードアクセス回数はO(logX)である。 ウ: 誤り。Xのオーダはインデックスを使わない線形探索(全件走査)の場合である。 エ: 誤り。X!(階乗)のオーダは巡回セールスマン問題の全列挙のような組合せ爆発の場合であり、検索アクセス回数とは無関係である。 💡 「平衡木の探索=O(log n)」は頻出の定石。線形探索O(n)、2分探索・B木系O(log n)、ハッシュO(1)の対比で覚えておくと計算量問題に強くなる。