Big O 記法について

はじめに

• コンピューターサイエンス初学者の初投稿です。
• Big O 記法について学んだのでそのまとめです。
• 間違っている場所もあるかもしれません。

O(1)

配列の添字でアクセスを行う
計算が最も少ない

  public void func1() {
    int[] ints = new int[]{1, 2, 3, 4, 5};

    System.out.println(ints[0]);
  }

出力結果

1

O(n)

配列の個数分処理を行う
そのため、配列が長くなれば長くなるほど処理時間が増えていく

  public void func2() {
    int[] ints = new int[]{1, 2, 3, 4, 5};

    for (int i : ints) {
      System.out.print(i + " ");
    }
  }

出力結果

1 2 3 4 5

O(n * n)

配列の個数２乗分の処理を行う
O(n)と同様に、配列の長さで処理が変わるがnの２乗のため、大幅に計算量が変わる

  public void func3() {
    int[] ints = new int[]{1, 2, 3, 4, 5};

    for (int i : ints) {
      for (int j : ints) {
        System.out.print(i + "-" + j + " ");
      }
      System.out.println();
    }
  }

出力結果

1-1 1-2 1-3 1-4 1-5 
2-1 2-2 2-3 2-4 2-5 
3-1 3-2 3-3 3-4 3-5 
4-1 4-2 4-3 4-4 4-5 
5-1 5-2 5-3 5-4 5-5 

O(log(n))

分割を行った後に処理を行う
O(1)へと収束が発生するのでO(n)ほど処理回数は多くない

  func4(10);

  public static void func4(int number) {
    if (number <= 1) {
      return;
    }

    System.out.println(number);

    func4(number / 2);
  }

出力結果

10
5
2

最後に

まだまだ奥が深そうだが、ひとまず自分の理解したところまで

参考資料

現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門