テクノロジ系出題頻度 3/3
計算量
けいさんりょう
定義
アルゴリズムの実行時間や使用メモリの規模を入力サイズの関数で表したもの。
詳細解説
時間計算量と空間計算量に大別される。最悪・平均・最良ケースを区別し、漸近的に O 記法、Ω 記法、Θ 記法で表現する。例えば線形探索はO(n)、二分探索はO(log n)、バブルソートはO(n²)、マージソートはO(n log n)、最短経路のダイクストラはO((V+E)log V)。計算量は同じアルゴリズムでもデータ構造により変わり、設計選択の重要指標。P・NP・NP困難等の計算複雑性理論の基礎概念。
「計算量」が出る問題に挑戦
読んだ内容は“思い出す”ほど記憶に残ります。解答・解説つき・基本無料で確認できます。
n個のデータをクイックソートで整列する場合の平均計算量として、正しいものはどれか。
二分探索の計算量として、正しいものはどれか。
O記法において、O(n^2)とO(n log n)を比較したとき、nが大きくなるにつれて計算量が小さいのはどちらか。
関連用語
よくある質問
Q. 計算量とは何ですか？
A. アルゴリズムの実行時間や使用メモリの規模を入力サイズの関数で表したもの。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。