レッスン 3・基礎理論 — 図書館塔
アルゴリズムと計算量
探索・ソートと計算量(O 記法)の基礎
- 1. 導入の会話
- 2. 参考書
- 3. レッスン演習(5問)

エン
参考書
IPA 中分類: アルゴリズムとプログラミング
このレッスンで学ぶこと
- O 記法の意味を説明できる
- 代表的な計算量(O(1)、O(n)、O(n log n)、O(n²))を理解する
- 探索・ソートの基本を知る
- レッスン演習(5問)の正解根拠を説明できる
O 記法
データ数 n に対する処理時間の 増え方のオーダー を表す。定数係数は無視。
記法
O(1)
意味
定数時間
例
先頭要素参照
記法
O(n)
意味
n に比例
例
線形探索
記法
O(n log n)
意味
n log n に比例
例
マージソート
記法
O(n²)
意味
n² に比例
例
二重ループ全比較
試験でのポイント
詳しく見る閉じる
マージソート・ヒープソート = O(n log n)(q037 正解)
バブルソート等の単純ソート = O(n²)
用語集
- アルゴリズム
- 問題を解くための手順・方法。
- 計算量
- 入力サイズに対する処理時間・メモリの増え方。
試験の出題ポイント
- 効率的なソート = O(n log n)(q037 正解)
- 二重ループ全比較 = O(n²)
理解度チェック
- O 記法の意味を説明できる
- 代表的な計算量を対応づけできる
- レッスン演習(5問)の正解理由を説明できる
レッスン演習(5問)
このレッスンの内容だけを出題します。全問正解でレッスンを終えたことになります(ログインが必要です)。