タグ: 計算量

計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る時間計算量・空間計算量を計算モデルから定義し、O・Ω・Θ 記法を関数の集合として厳密に述べる。増大度の階層を証明し、O(1) から O(2^n) までの各クラスが入力サイズの増大にどう耐えるかを定理と数値で比較する。情報科学アルゴリズムとデータ構造学部計算量 O記法漸近解析マスター定理約 30 分
探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1)本ソート済み配列に対する二分探索が O(log n) で終わる理由を不変条件と決定木の下界から示し、ハッシュ表がチェイン法とオープンアドレス法で平均 O(1) を実現する仕組みと、その「平均」の中身を明らかにする。情報科学アルゴリズムとデータ構造学部二分探索ハッシュ表計算量衝突解決約 13 分
ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」バブルソートが二乗時間になる理由を転倒数で説明し、マージソートの分割統治が n log n を達成することを証明する。クイックソートの平均計算量と最悪計算量の差がピボットの選び方から生じる仕組みまで扱う。情報科学アルゴリズムとデータ構造学部ソート分割統治法計算量クイックソート約 25 分