ブロック分割した整列表の平均比較回数

テクノロジ難易度: ★★★☆☆

異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、m は十分大きく、n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。

出典: 令和7年度秋期 応用情報技術者 午前 問6
📊ログインすると挑戦履歴を記録できます
🎉 無料キャンペーン中:いまならログインするだけで全機能を無料でご利用いただけます(秋試験まで)。

「テクノロジ」分野の関連問題