2009年に「計算量を具体的に見てみる」という、処理から計算量を視覚化するブログを書いてた。
計算量を具体的に見てみる - きしだのHatena
これJava 6時代なので、Java 25で書き直してみた。
より詳しい解説は元ブログのほうを見てください。
O(1)
まず基本のO(1)です。処理量が入力量によらない場合ですね。
この例でいえば、処理がnを使わない場合。
あと、動的配列の拡張で、配列のサイズを2倍にしていくとそれ自体の計算量はO(n)になるのだけど、拡張が起きるのはlog n回になるので、平均するとO(1)というものもありますね。
表示コードを最後に書いてましたが、importが1行、クラスが不要、ラムダ式が使えるってことでだいぶコンパクトになったのでそのまま書いてます。
import module java.desktop;
void main() {
show("O(1)", 1,
(n, proc) -> proc.run());
}
void show(String title, double range, BiConsumer<Integer, Runnable> exec) {
var f = new JFrame(title);
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(408, 333);
int ORX = 30; int ORY = 280;
var img = new BufferedImage(400, 300, BufferedImage.TYPE_INT_RGB);
var g = img.createGraphics();
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
g.setColor(Color.WHITE);
g.fillRect(0, 0, 400, 300);
g.setColor(Color.BLACK);
g.drawLine(ORX, 30, ORX, ORY);
g.drawLine(ORX, ORY, 380, ORY);
var path = new GeneralPath();
for (int i = 1; i < 350; ++i) {
int[] count = {0};
exec.accept(i, () -> count[0]++);
var c = count[0] * 30 * 250 / 350 * range;
var y = Math.max(0, ORY - c);
if (i == 1) {
path.moveTo(i + ORX, y);
} else {
path.lineTo(i + ORX, y);
}
if (y <= 0) break;
}
g.setStroke(new BasicStroke(2));
g.setColor(Color.RED);
g.draw(path);
g.dispose();
var label = new JLabel(new ImageIcon(img));
f.add(label);
f.setVisible(true);
}
O(log n)
処理を行うたびに入力を何割か減らせるアルゴリズムの計算量ですね。二分探索など。四則演算も桁数だけ時間がかかるので数値nに対する計算量がO(log n)になります。
void compute(int n, Runnable proc) {
proc.run();
if (n == 1) return;
compute(n / 2, proc);
}
void main() {
show("O(log n)", 1, this::compute);
}
O(n)
O(n)は入力の量に比例して時間がかかるアルゴリズムですね。ふつうにn回繰り返すやつ。
void compute(int n, Runnable proc) {
for (int i = 0; i < n; ++i) {
proc.run();
}
}
void main() {
show("O(n)", 1 / 30., this::compute);
}
O(n log n)
O(n log n)はO(n)の処理をlog n回繰り返す処理です。というと難しそうだけど、ソートですね。そして、ソートを前処理に使うアルゴリズムがO(n log n)以上の計算量になります。
void compute(int n, Runnable proc) {
for (int i = 0; i < n; ++i) {
proc.run();
}
if (n <= 1) return;
compute(n / 2, proc);
compute(n - n / 2, proc);
}
void main() {
show("O(n log n)", 1 / 200., this::compute);
}
O(n ^ 2)
O(n ^ 2)になるアルゴリズムは、要素のすべての組み合わせを処理するようなアルゴリズムですね。
二重ループがあります。
void compute(int n, Runnable proc) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
proc.run();
}
}
}
void main() {
show("O(n ^ 2", 1 / 3000., this::compute);
}
O(2 ^ n)
すべての組み合わせについて処理するような場合です。計算がむずかしくなりがち。
void compute(int n, Runnable proc) {
if (n <= 0) return;
proc.run();
compute(n - 1, proc);
compute(n - 1, proc);
}
void main() {
show("O(2 ^ n)", 1 / 3000., this::compute);
}
nビットの数だけ処理を走らせるような場合ともいえるので、次のようにも書けます。
void compute(int n, Runnable proc) {
long count = 2 << n;
for (long i = 0; i < count; ++i) {
proc.run();
}
}
O(n!)
すべての順序について処理する場合です。最短経路を求める場合とか。基本的に計算がおわりません。
void compute(int n, Runnable proc) {
if (n <= 0) return;
proc.run();
for (int i = 0; i < n; ++i) {
compute(n - 1, proc);
}
}
void main() {
show("O(n!)", 1 / 5000., this::compute);
}
本
計算量の話なら、乱択ガール
もっと物語的であれば、「最短経路の本」
ちょっとガチめにやるなら「計算理論の基礎」
3版が出てるのだな。
計算理論の基礎 [原著第3版] 1.オートマトンと言語
計算理論の基礎 [原著第3版] 2.計算可能性の理論
![計算理論の基礎 [原著第3版] 3.複雑さの理論](https://m.media-amazon.com/images/I/51GpvG33YLL._SL500_.jpg "計算理論の基礎 [原著第3版] 3.複雑さの理論")
