APG4b Java版 第2章: 実践的な書き方と計算量
2.00. 第2章について
第1章の内容をマスターすることで、理論上すべての計算処理を行うプログラムを書けるようになりました。
第2章では、複雑な計算をどのように記述するか、また Java に固有の便利な書き方を説明します。さらに、実行時間の見積もりに使う「計算量」の概念を学びます。第2章をマスターすると、実際にほぼすべての計算処理プログラムを実用的に書けるようになります。
AtCoder での練習について:
- AtCoder Beginner Contest (ABC) ... 毎週土曜夜に開催
- AtCoder Daily Training (ADT) ... 過去問を使ったバーチャルコンテスト
- AtCoder 強化プラン ... コンテストの復習や別の学習法
2.01. いろいろな for 文
キーポイント
- インデックス付き for:
for (int i = 0; i < N; i++) - 拡張 for 文 (foreach):
for (型 変数 : コレクション) - 複数リストを同時にループ: インデックスを使う
breakでループを抜ける、continueで次のイテレーションへ
第1章では基本的な for 文を学びました。この節では、様々な状況に対応できるよう for 文の使い方をさらに掘り下げます。
基本の for 文パターン
range(stop) の代わり (0 から N-1 まで):
Python の for i in range(5): に対応する書き方です。
for (int i = 0; i < 5; i++) {
System.out.println(i);
}実行結果:
0
1
2
3
4range(start, stop) の代わり (start から stop-1 まで):
Python の for i in range(2, 5): に対応します。
for (int i = 2; i < 5; i++) {
System.out.println(i);
}実行結果:
2
3
4range(start, stop, step) の代わり (start から step ずつ増やして stop 未満まで):
Python の for i in range(4, 10, 2): に対応します。
for (int i = 4; i < 10; i += 2) {
System.out.println(i);
}実行結果:
4
6
8逆順 (Python の reversed() / range(5, -1, -1)):
for (int i = 5; i >= 0; i--) {
System.out.println(i);
}実行結果:
5
4
3
2
1
0配列・ArrayList に対する for 文
配列や ArrayList の全要素を順番に処理するには「拡張 for 文」が便利です。Python の for x in L: に対応します。
配列に対する拡張 for 文:
int[] a = {3, 1, 4, 1, 5};
for (int x : a) {
System.out.println(x);
}実行結果:
3
1
4
1
5for (int x : a) は「配列 a の先頭から順番に各要素を x に格納して処理する」という意味です。インデックスが不要な場合は拡張 for 文が読みやすくなります。
文字列の各文字を処理:
文字列を toCharArray() で char の配列に変換してから拡張 for 文を使います。
String s = "AtCoder";
for (char c : s.toCharArray()) {
System.out.println(c);
}実行結果:
A
t
C
o
d
e
r2次元配列のアンパック (Python の for a, b in [[5, 10], [6, 20]]:):
Java では Python のようなタプルアンパックはできませんが、配列の要素に直接アクセスできます。
int[][] pairs = {{5, 10}, {6, 20}};
for (int[] pair : pairs) {
int a = pair[0], b = pair[1];
System.out.println(a + " " + b);
}実行結果:
5 10
6 20インデックスと値を同時に処理 (Python の enumerate())
Java には enumerate() に相当する機能がないため、インデックスを手動で管理します。
int[] a = {10, 20, 30};
for (int i = 0; i < a.length; i++) {
System.out.println(i + " " + a[i]);
}実行結果:
0 10
1 20
2 30インデックス i と値 a[i] を同時に使いたいときはこのパターンを使います。
逆順の for (Python の reversed())
配列を逆順に処理するには、インデックスを末尾から先頭に向かって動かします。
int[] a = {3, 1, 4, 1, 5};
for (int i = a.length - 1; i >= 0; i--) {
System.out.println(a[i]);
}実行結果:
5
1
4
1
3a.length - 1 が最後のインデックス (配列長 - 1) です。i >= 0 の条件なので i = 0 (先頭) まで処理します。
複数配列の同時ループ (Python の zip())
Java には zip() がないため、インデックスを共通で使います。
int[] A = {1, 2, 3};
int[] B = {10, 20, 30};
for (int i = 0; i < A.length; i++) {
System.out.println(A[i] + " " + B[i]);
}実行結果:
1 10
2 20
3 30インデックス i を使って A[i] と B[i] を同時に参照しています。このパターンは2つの配列を並行して処理するときに頻繁に使います。
break と continue
break はループを即座に抜け、continue はそのイテレーションの残り処理をスキップして次に進みます。
// break: ループを抜ける
for (int i = 0; i < 5; i++) {
if (i == 3) break;
System.out.println(i);
}
// 出力: 0, 1, 2// continue: 次のイテレーションへスキップ
for (int i = 0; i < 5; i++) {
if (i == 3) continue;
System.out.println(i);
}
// 出力: 0, 1, 2, 4ラベル付き break
Java ではラベル付き break を使って、外側のループを直接抜けることができます。Python には for-else がありますが Java には対応する構文がなく、ラベル付き break が代替になります。
outer:
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (i + j == 5) {
System.out.println("抜ける: " + i + " " + j);
break outer; // outer ラベルのループを抜ける
}
}
}
System.out.println("終了");実行結果:
抜ける: 0 5
終了break outer; は内側のループだけでなく、outer: とラベルが付いた外側のループも同時に抜けます。break; だけでは内側のループのみを抜けるため、この違いに注意してください。
練習問題
EX14. 隣り合う同じ値を探す
2.02. 多重ループ
キーポイント
- ループの中にさらにループを書くことを「多重ループ」という
- 内側のループで
breakすると内側のループのみ抜ける - 複数段階のループを抜けるには「ラベル付き break」または「フラグ変数」を使う
- Python と同様の書き方が使える
多重ループとは
ループの中にさらにループを書いたものを「多重ループ」(または「入れ子ループ」「ネストしたループ」) といいます。表の全セルを処理したり、すべての組み合わせを列挙したりするときに使います。
基本: 二重ループ
外側のループが1回実行されるたびに、内側のループが最初から最後まで実行されます。
public class Main {
public static void main(String[] args) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(i + " " + j);
}
}
}
}実行結果:
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2外側のループの i が 0 のとき、内側のループの j が 0, 1, 2 と変化します。i が 1, 2 のときも同様です。合計 3 × 3 = 9 回の出力が行われます。
実践例: 2つの数列に共通要素があるか判定
以下のプログラムは、配列 A と配列 B に共通の要素が存在するかどうかを判定します。すべての組み合わせ (A[i], B[j]) を二重ループで確認しています。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] A = new int[3];
int[] B = new int[3];
for (int i = 0; i < 3; i++) A[i] = sc.nextInt();
for (int i = 0; i < 3; i++) B[i] = sc.nextInt();
boolean answer = false; // 共通要素が見つかったかどうか
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (A[i] == B[j]) {
answer = true; // 一致した!
}
}
}
if (answer) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}このプログラムでは、A の各要素と B の各要素のすべての組み合わせをチェックしています。A と B がそれぞれ3要素なら、合計 3 × 3 = 9 通りの比較を行います。
break の動作: 内側のループのみ抜ける
二重ループの内側で break を使うと、内側のループのみを抜けます。外側のループはそのまま継続します。
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (j == 1) break; // 内側の j ループのみ抜ける
System.out.println(i + " " + j);
}
}実行結果:
0 0
1 0
2 0i = 0 のとき: j = 0 を処理 → j = 1 で break → 内側ループ終了 → 外側ループ継続 i = 1 のとき: j = 0 を処理 → j = 1 で break → ... i = 2 のとき: 同様
このように、各 i について j = 0 だけが処理され、j = 1 で常に内側ループを抜けます。
複数段階のループから抜ける方法1: フラグ変数
外側のループも含めて抜けたい場合、フラグ変数 (boolean) を使う方法があります。
boolean finished = false;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(i + " " + j);
if (i == 1 && j == 1) {
finished = true;
}
if (finished) break; // 内側ループを抜ける
}
if (finished) break; // 外側ループも抜ける
}finished が true になったとき、まず内側の break で内側ループを抜け、外側ループの if (finished) break で外側ループも抜けます。
複数段階のループから抜ける方法2: ラベル付き break (Java の利点)
ラベル付き break を使うと、フラグ変数を使わずにすっきり書けます。
outer:
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(i + " " + j);
if (i == 1 && j == 1) {
break outer; // outer ラベルのループを一気に抜ける
}
}
}break outer; は outer: でラベルを付けたループを直接抜けます。フラグ変数が不要で、コードがシンプルになります。
複数段階のループから抜ける方法3: メソッド化して return
ループ処理をメソッドに分離して、return でメソッドを終了させる方法もあります。
public class Main {
static void func() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == 1 && j == 1) return; // メソッドを終了 (全ループから抜ける)
System.out.println(i + " " + j);
}
}
}
public static void main(String[] args) {
func();
}
}実行結果:
0 0
0 1
0 2
1 0i == 1, j == 1 になった時点で return によりメソッド自体が終了するため、すべてのループから抜けた状態になります。
練習問題
EX15. 果物屋さんでお買い物
2.03. ループによるリスト生成 (内包表記の代替)
キーポイント
- Java には Python のリスト内包表記がない
- 代わりに
forループでArrayListにadd()するか、配列を使う - Java 8 以降の Stream API を使うと内包表記に近い書き方ができる
- ただし競技プログラミングでは従来の
forループが読みやすく速い
リスト内包表記とは
Python では [i * i for i in range(5)] のように、1行でリストを生成できる「リスト内包表記」があります。Java にはこの機能がありませんが、for ループを使って同等の処理が書けます。
Python の内包表記と Java の対応
Python の [i * i for i in range(5)] :
Java (for ループ + ArrayList 版):
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < 5; i++) {
result.add(i * i); // i の 2 乗を追加
}
System.out.println(result); // [0, 1, 4, 9, 16]
}
}実行結果:
[0, 1, 4, 9, 16]i が 0, 1, 2, 3, 4 と変化し、それぞれの 2 乗 (0, 1, 4, 9, 16) を result に追加しています。
Java (配列版) :
サイズが事前にわかっている場合は配列の方が高速です。
int[] result = new int[5];
for (int i = 0; i < 5; i++) {
result[i] = i * i;
}
// 出力: 0 1 4 9 16
for (int x : result) System.out.print(x + " ");
System.out.println();条件付きフィルタリング (Python の [x for x in a if x % 2 == 0])
Python ではリスト内包表記に if を組み合わせることができます。Java では for ループの中で if でチェックします。
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
ArrayList<Integer> evens = new ArrayList<>();
for (int x : a) {
if (x % 2 == 0) { // 偶数なら
evens.add(x); // リストに追加
}
}
System.out.println(evens); // [2, 4, 6, 8]
}
}実行結果:
[2, 4, 6, 8]a の各要素 x に対して、x % 2 == 0 (偶数) の条件が true のときだけ evens に追加しています。
組み込み関数との組み合わせ
Python の sum([i*i for i in range(N)]) :
int N = 5;
int sum = 0;
for (int i = 0; i < N; i++) {
sum += i * i; // i の 2 乗を足す
}
System.out.println(sum); // 0 + 1 + 4 + 9 + 16 = 30内包表記でリストを作ってから sum() を呼ぶ代わりに、ループ内で直接足し算を行います。
最大値・最小値:
int[] a = {3, 1, 4, 1, 5, 9, 2, 6};
int maxVal = a[0]; // 最初の要素を仮の最大値にする
int minVal = a[0]; // 最初の要素を仮の最小値にする
for (int x : a) {
maxVal = Math.max(maxVal, x); // より大きければ更新
minVal = Math.min(minVal, x); // より小さければ更新
}
System.out.println("max=" + maxVal + " min=" + minVal);実行結果:
max=9 min=1Stream API を使った内包表記風の書き方 (参考)
Java 8 以降では Stream API を使って内包表記に近い書き方ができます。競技プログラミングでは使う場面が限られますが、知っておくと便利です。
import java.util.Arrays;
import java.util.stream.*;
public class Main {
public static void main(String[] args) {
// [i*i for i in range(5)] の代わり
int[] result = IntStream.range(0, 5).map(i -> i * i).toArray();
System.out.println(Arrays.toString(result)); // [0, 1, 4, 9, 16]
// sum([i*i for i in range(5)]) の代わり
int sum = IntStream.range(0, 5).map(i -> i * i).sum();
System.out.println(sum); // 30
// [x for x in a if x % 2 == 0] の代わり
int[] a = {1, 2, 3, 4, 5, 6};
int[] evens = Arrays.stream(a).filter(x -> x % 2 == 0).toArray();
System.out.println(Arrays.toString(evens)); // [2, 4, 6]
}
}ただし競技プログラミングでは、従来の for ループの方がシンプルで速いことが多いため、無理に Stream API を使う必要はありません。
入力のリスト読み込み
Python の list(map(int, input().split())) に対応する Java の書き方:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 5;
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = sc.nextInt();
}
// これで a[0], a[1], ..., a[N-1] に読み込まれる
}
}練習問題
EX16. 英単語テストの練習
2.04. 多次元配列
キーポイント
- 2次元配列は
int[][] a = new int[N][M]で宣言 a[i][j]で i 行 j 列の要素にアクセスa.lengthで行数、a[0].lengthで列数を取得ArrayList<ArrayList<Integer>>で可変長の2次元リストも作れる
多次元配列とは
配列の各要素がさらに配列であるものを「多次元配列」といいます。表形式のデータや行列を扱う場合によく使います。
Python の「リストのリスト」[[1, 2, 3], [4, 5, 6]] に対応します。
2次元配列の基本
public class Main {
public static void main(String[] args) {
int[][] a = {{1, 3, 5}, {2, 4, 6}};
// 1行目 2行目
System.out.println(a[0][0]); // 1 (0行0列)
System.out.println(a[1][1]); // 4 (1行1列)
System.out.println(a[0][2]); // 5 (0行2列 = 1行目の最後)
System.out.println(a.length); // 2 (行数)
System.out.println(a[0].length); // 3 (列数)
}
}実行結果:
1
4
5
2
3a[i][j] の i は行番号 (0から)、j は列番号 (0から) です。
二重ループと2次元配列
2次元配列の全要素を処理するには、行と列それぞれにループを使います。
int[][] a = {{1, 3, 5}, {2, 4, 6}};
for (int i = 0; i < a.length; i++) {
System.out.print("リストの第 " + i + " 成分は [");
for (int j = 0; j < a[i].length; j++) {
if (j > 0) System.out.print(", ");
System.out.print(a[i][j]);
}
System.out.println("]");
}実行結果:
リストの第 0 成分は [1, 3, 5]
リストの第 1 成分は [2, 4, 6]外側のループが行を、内側のループが列を担当しています。
入力から2次元配列を作成
N 行 M 列の2次元配列を入力から作成します。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 行数
int M = sc.nextInt(); // 列数
int[][] a = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
a[i][j] = sc.nextInt(); // 1つずつ読み込む
}
}
}
}入力例 (3行2列):
3 2
1 2
3 4
5 6a[0] = {1, 2}, a[1] = {3, 4}, a[2] = {5, 6} という配列が作られます。
すべて 0 の N×M 配列
int N = 2, M = 3;
int[][] a = new int[N][M]; // 自動的に 0 で初期化される
// a = {{0,0,0},{0,0,0}}Java の int[][] は自動的に 0 で初期化されます。Python の [[0]*M for _ in range(N)] に対応しますが、Java の方が安全です (Pythonの [[0]*M]*N は同じ行を共有するバグが起きやすい)。
可変長の2次元リスト
グラフの隣接リストなど、各行の長さが異なる場合は ArrayList<ArrayList<Integer>> を使います。
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
int N = 4;
// N 個の空の ArrayList を持つ ArrayList を作成
ArrayList<ArrayList<Integer>> a = new ArrayList<>();
for (int i = 0; i < N; i++) {
a.add(new ArrayList<>());
}
a.get(0).add(10); // 0番目のリストに追加
a.get(0).add(20);
a.get(2).add(30); // 2番目のリストに追加
a.get(3).add(40);
a.get(3).add(50);
a.get(3).add(60);
// 結果: [[10, 20], [], [30], [40, 50, 60]]
for (ArrayList<Integer> row : a) {
System.out.println(row);
}
}
}実行結果:
[10, 20]
[]
[30]
[40, 50, 60]グラフの隣接リスト表現などで、各ノードに接続する辺の情報を格納するときによく使うパターンです。
Python の2次元リストの罠
Python では [[0]*M]*N で2次元リストを作ると、各行が同じオブジェクトを参照するため、1か所を変更すると全行が変わるバグが起きます。Java の int[][] ではこの問題は起きません。
int N = 3, M = 2;
int[][] a = new int[N][M]; // 各行が独立した配列 (安全)
a[0][0] = 1;
System.out.println(a[1][0]); // 0 (他の行は影響を受けない)3次元配列
3次元配列も同様に定義できます。
int N = 2, M = 2, D = 2;
int[][][] lst3d = new int[N][M][D];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < D; k++) {
lst3d[i][j][k] = i * 100 + j * 10 + k;
}
}
}
// [[[0,1],[10,11]],[[100,101],[110,111]]]練習問題
EX17. ゲーム大会
2.05. 再帰メソッド
キーポイント
- メソッドが自分自身を呼び出すことを「再帰呼び出し」という
- 再帰メソッドには「ベースケース」と「再帰呼び出し」の2つの部分がある
- Java のデフォルトのスタックサイズは JVM に依存 (約 500〜1000 回程度が安全)
- 深い再帰には
StackOverflowErrorが発生する
再帰とは
「再帰」とは、あるメソッドが自分自身を呼び出す処理のことです。複雑な問題を「より小さな同じ種類の問題」に分解して解くときに使います。
再帰メソッドの基本
1 から N までの合計 (三角数) を求める再帰メソッドです。
public class Main {
static long sumTriangle(int n) {
if (n == 0) return 0; // ベースケース: n=0 のとき答えは 0
long s = sumTriangle(n - 1); // 再帰呼び出し: n-1 までの合計を求める
return s + n; // 答えの計算: n-1 までの合計に n を加える
}
public static void main(String[] args) {
System.out.println(sumTriangle(10)); // 55
}
}実行の流れ (n=3 の場合):
sumTriangle(3)が呼ばれるsumTriangle(2)を呼ぶ (まだ結果待ち)sumTriangle(1)を呼ぶ (まだ結果待ち)sumTriangle(0)を呼ぶ → ベースケースで0を返すsumTriangle(1)に戻る →0 + 1 = 1を返すsumTriangle(2)に戻る →1 + 2 = 3を返すsumTriangle(3)に戻る →3 + 3 = 6を返す → 出力:6
再帰メソッドの3つの部分
- ベースケース: 再帰呼び出しなしに直接答えを求める最小ケース (無限再帰を防ぐために必須)
- 再帰呼び出し: より小さなケースを呼び出す
- 答えの計算: 再帰結果を利用して最終答えを計算
すべての再帰メソッドはこの3つの要素で構成されています。ベースケースがないと無限ループになってしまうので注意してください。
階乗
n の階乗 (n!) を再帰で求めます。n! = n × (n-1) × ... × 1 です。
static long factorial(int n) {
if (n == 0 || n == 1) return 1; // ベースケース: 0! = 1! = 1
return n * factorial(n - 1); // n! = n × (n-1)!
}実行の流れ (n=4):
factorial(4)=4 * factorial(3)factorial(3)=3 * factorial(2)factorial(2)=2 * factorial(1)factorial(1)=1(ベースケース)- 戻ってくると:
2 * 1 = 2,3 * 2 = 6,4 * 6 = 24
フィボナッチ数
フィボナッチ数列 (1, 1, 2, 3, 5, 8, 13, ...) の n 番目を求めます。
static long fib(int n) {
if (n == 0 || n == 1) return 1; // ベースケース
return fib(n - 1) + fib(n - 2); // fib(n) = fib(n-1) + fib(n-2)
}注意: この実装は同じ計算が何度も行われるため非常に遅いです (n が大きいと指数的に時間がかかる)。メモ化 (第4章) を使うと高速化できます。
各桁の和
整数 n の各桁の数字を合計する再帰メソッドです。
static int digitSum(int n) {
if (n <= 9) return n; // ベースケース: 1桁ならそのまま
int ones = n % 10; // 1の位の数字
int other = n / 10; // 1の位を除いた残り
return digitSum(other) + ones; // 残りの桁の和 + 1の位
}例: n = 123 の場合
ones = 3,other = 12digitSum(12) + 3ones = 2,other = 1digitSum(1) + 2=1 + 2 = 3
3 + 3 = 6→ 1 + 2 + 3 = 6
例題: 報告書の伝達時間
木構造 (ツリー) における報告書の伝達時間を再帰で求める問題です。
import java.util.*;
public class Main {
static ArrayList<ArrayList<Integer>> children; // 各ノードの子ノードリスト
static int completeTime(int x) {
if (children.get(x).isEmpty()) return 0; // 葉ノードなら時間は0
int maxTime = 0;
for (int y : children.get(x)) {
// 子ノード y の処理時間 + 1 の最大値
maxTime = Math.max(maxTime, completeTime(y) + 1);
}
return maxTime;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] p = new int[N];
p[0] = -1; // ルートの親は存在しない
for (int i = 1; i < N; i++) p[i] = sc.nextInt();
children = new ArrayList<>();
for (int i = 0; i < N; i++) children.add(new ArrayList<>());
for (int i = 1; i < N; i++) children.get(p[i]).add(i);
System.out.println(completeTime(0)); // ルートから処理
}
}入力: 6 / 0 0 1 1 4出力: 3
再帰メソッドの注意点
スタックオーバーフロー:
再帰が深くなりすぎると StackOverflowError が発生します。
// 深すぎる再帰は StackOverflowError を引き起こす
static void infiniteRecursion() {
infiniteRecursion(); // 終了条件がない → StackOverflowError
}競技プログラミングでは再帰が深くなる場合、反復 (ループ) に書き換えるか、スタック (ArrayDeque) を使って手動で管理することを検討します。
クイックソートの例
再帰を使ったソートアルゴリズムの例として、クイックソートを示します。
import java.util.*;
public class Main {
static ArrayList<Integer> quickSort(ArrayList<Integer> a) {
if (a.isEmpty()) return new ArrayList<>(); // ベースケース: 空なら終了
int p = a.remove(a.size() - 1); // ピボットを取り出す
ArrayList<Integer> lo = new ArrayList<>(); // ピボット未満
ArrayList<Integer> hi = new ArrayList<>(); // ピボット以上
for (int x : a) {
if (x < p) lo.add(x);
else hi.add(x);
}
// lo をソート、ピボット、hi をソートして結合
ArrayList<Integer> result = quickSort(lo);
result.add(p);
result.addAll(quickSort(hi));
return result;
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));
System.out.println(quickSort(list)); // [1, 1, 2, 3, 4, 5, 6, 9]
}
}練習問題
EX18. 報告書の枚数
2.06. 計算量
キーポイント
- アルゴリズム: 処理の計算手順
- 計算量: 入力に対して必要な計算時間・メモリがどう変化するかの指標
- 時間計算量: 計算ステップ数の変化
- 空間計算量: メモリ使用量の変化
- オーダー記法 O(...): 計算量を大まかに表す記法
- Java は Python より定数倍が速い (同じ O(N) でも 10〜100 倍速)
アルゴリズムとは
「ある処理を行うときに、どのような計算を行っていくかという計算手順」をアルゴリズムといいます。同じ問題を解くにも、速いアルゴリズムと遅いアルゴリズムがあります。
例: 1から100までの総和
- アルゴリズムA: 順に足す →
1 + 2 + 3 + ... + 100(99回の加算) - アルゴリズムB: 公式を使う →
N * (N + 1) / 2(3回の計算)
Nが大きくなればなるほど、アルゴリズムBが圧倒的に速くなります。
オーダー記法の求め方
計算量を正確に求めるのは難しいため、「だいたいの大きさ」を表す「オーダー記法」を使います。
- 係数を省略する (定数については 1 とする)
- N を大きくしたとき一番影響が大きい項を取り出し、O(項) と書く
例:
N + 100→ O(N) (定数100は省略)10N + N³→ O(N³) (最も大きい項)3 + 5→ O(1) (定数)2ᴺ + N²→ O(2ᴺ)
主な計算量の種類
O(1): 定数時間
入力サイズに関わらず一定時間で処理できます。最も速いです。
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
long s = N * (N + 1) / 2; // 公式で一発計算
System.out.println(s);O(N): 線形時間
入力サイズ N に比例した時間がかかります。
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++) a[i] = sc.nextInt(); // N 回の読み込み
int cnt = 0;
for (int x : a) { // N 回のループ
if (x % 2 == 0) cnt++;
}
System.out.println(cnt);N が 2 倍になると処理時間も約 2 倍になります。
O(N²): 二乗時間
二重ループなどで生じます。N が大きくなると急激に遅くなります。
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] table = new int[N][N];
for (int i = 0; i < N; i++) { // N 回
for (int j = 0; j < N; j++) { // さらに N 回 → 合計 N² 回
table[i][j] = (i + 1) * (j + 1);
}
}
for (int[] row : table) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < row.length; j++) {
if (j > 0) sb.append(" ");
sb.append(row[j]);
}
System.out.println(sb);
}N が 2 倍になると処理時間は約 4 倍になります。
O(log N): 対数時間
入力サイズが2倍になっても、処理回数が1回しか増えません。非常に速いです。
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int cnt = 0;
while (N % 2 == 0) { // N が 2 で割り切れる間
cnt++;
N /= 2; // N を半分に
}
System.out.println(cnt);N = 1024 のとき、10回のループで完了します (1024 → 512 → ... → 1)。
計算量の大小関係
O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ᴺ)入力 N と実行時間の目安
| N | O(1) | O(log N) | O(N) | O(N log N) | O(N²) | O(2ᴺ) |
|---|---|---|---|---|---|---|
| 1 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 |
| 10 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 |
| 1,000 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 0.01秒 | 地球爆発 |
| 10⁶ | 一瞬 | 一瞬 | 0.01秒 | 0.2秒 | 3時間 | 地球爆発 |
| 10⁸ | 一瞬 | 一瞬 | 1秒 | 30秒 | 3年 | 地球爆発 |
| 10¹⁶ | 一瞬 | 一瞬 | 3年 | 170年 | 地球爆発 | 地球爆発 |
AtCoder の問題では実行時間制約が 2秒〜5秒であることが多いです。Java では 1秒あたり約 10⁸ 回の計算ができます (Python の約 10〜50 倍速)。
問題文の N の制約から適切な計算量のアルゴリズムを選ぶ必要があります:
- N ≤ 10⁶ → O(N) や O(N log N) まで OK
- N ≤ 10⁴ → O(N²) まで OK
- N ≤ 20 → O(2ᴺ) でも OK
Java の高速化のヒント
出力を高速化する (PrintWriter を使う):
大量に System.out.println() を呼ぶと遅くなります。PrintWriter と BufferedWriter を組み合わせると高速になります。
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 0; i < 100000; i++) {
pw.println(i);
}
pw.flush(); // 忘れずに flush する
}
}入力を高速化する (BufferedReader を使う):
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
}
}よく使う操作の計算量
| 操作 | クラス | 計算量 |
|---|---|---|
a.length | 配列 | O(1) |
list.size() | ArrayList | O(1) |
list.get(i) | ArrayList | O(1) |
list.add(x) | ArrayList | O(1) |
list.contains(x) | ArrayList | O(N) |
Arrays.sort(a) | Arrays | O(N log N) |
Collections.sort(list) | Collections | O(N log N) |
Arrays.binarySearch(a, v) | Arrays | O(log N) |
練習問題
EX19. 計算量の見積もり