レッスン 3・基礎理論 — 図書館塔

アルゴリズムと計算量

探索・ソートと計算量(O 記法)の基礎

  1. 1. 導入の会話
  2. 2. 参考書
  3. 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問)

このレッスンの内容だけを出題します。全問正解でレッスンを終えたことになります(ログインが必要です)。