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

B⁺木は，全ての葉が根から同じ深さにある平衡木です。各ノードから多数の枝が出るため，木の高さはデータ総件数Xの対数に比例します。1件のデータを検索するときは根から葉までのノードを1つずつたどるので，アクセス回数は木の高さに比例し，オーダはlog Xになります。

• ア: √X
  誤り。平方根に比例するアクセス回数にはなりません。

• イ: log X
  正しい。B⁺木の高さはlog Xに比例するので，アクセス回数のオーダはlog Xです。

• ウ: X
  誤り。データを先頭から順に調べる線形探索のオーダです。

• エ: X!
  誤り。全ての並べ方を調べるような処理のオーダで，検索には当てはまりません。

答え

イ: log X