読み方のヒント

矢印ボタン(または ← → キー)でページを移動できます。

第5節 アルゴリズムと計算量

5.3 計算量とO記法

アルゴリズムの速さは、データの数nが増えたときに、処理の回数がどのように増えるかで比べます。これをO記法で表します。

表し方増え方例
O(1)nに関係なく一定配列の番号で1つ取り出す
O(log n)nが2倍になっても1回増えるだけ2分探索
O(n)nに比例線形探索、最大値を求める
O(n log n)nとlog nの積クイックソート(平均)
O(n²)nの2乗に比例選択ソート、バブルソート

データが10倍になると、O(n)の処理は約10倍、O(n²)の処理は約100倍の時間がかかります。

24 / 30