② アルゴリズムとプログラミング
基本情報技術者 第47問
問題
データ数nに関わらず処理回数が一定となる計算量のオーダーはどれか。
AO(log n)
BO(n)
CO(1)✓ 正解
DO(n log n)
正解
C：O(1)
解説
ハッシュ法による探索は、衝突がなければデータ数に関わらず一定時間で完了する。
分野解説：② アルゴリズムとプログラミング
データ構造とアルゴリズムを扱う分野で、科目B（旧午後）にも直結する重要領域です。配列・連結リスト・スタック・キュー・木構造（2分探索木）・ハッシュ法といったデータ構造の特徴と、線形探索・2分探索・クイックソートなどの探索・整列アルゴリズム、計算量オーダー（O(1)・O(n)・O(log n)）が頻出です。再帰・再入可能などプログラム特性やHTML・CSS・Ajaxといったマークアップ関連知識も問われます。
この分野の問題をすべて見る →本番形式で問題を解いてみよう
クイズモードで挑戦 →同じ分野の関連問題
基本情報技術者について
ITエンジニアの登竜門となる国家試験
| 主催 | 情報処理推進機構（IPA） |
|---|---|
| 出題形式 | 科目A 多肢選択式（四肢択一）60問／科目B 多肢選択式20問。CBT方式で通年実施 |
| 試験時間 | 科目A 90分・科目B 100分 |
| 受験料 | 7,500円（税込） |
| 合格基準 | 科目A・科目Bとも評価点600点以上／1,000点満点 |
| 難易度 | ★★★☆☆（標準） |
基本情報技術者の関連記事
1ヶ月か3ヶ月か、基本情報技術者の積み上げ方を決める
科目Aは広く浅く、科目Bは狭く深く。同じ試験でも二つの科目は攻め方が違います。基礎理論から計算のパターン化、暗記分野へと回す順番を、362問の分野別内訳とあわせて示します。
ITパスポートと応用情報の間にある壁：基本情報の実像
50〜100時間で届く人と、100〜200時間かかる人を分けているものは何か。11分野の広さと科目Bの思考力という二つの負荷から、★★★☆☆という評価の中身を分解していきます。
探索と整列の計算量から固める基本情報技術者の科目B
キャッシュのヒット率、稼働率、伝送時間といった計算は、型を持っているかどうかで所要時間が変わります。取り違えやすい用語の対比やセキュリティ・ネットワークの頻出語も、362問の演習と併用する前提で。