시간복잡도를 자바로 구현

1. 시간복잡도

시간복잡도는 알고리즘, 자료구조를 공부하게되면 접하게되면 단어이다.

그렇다면 시간복잡도는 무엇인가? 쉽게 말해 지금 내 코드의 실행 시간을 Big O (빅-오) 표기법: O(N) 표기법으로 표현을 한 것이다.

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 공부하면 된다.

 

1.1. 대문자 O 표기법 및 게산 방법

• 입력 n 에 따라 결정되는 시간 복잡도 함수

• O(1), O($log n$), O(n), O(n $log n$), O($n^2$), O($2^n$), O(n!)등으로 표기함

• 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.

O(1) < O($log n$) < O(n) < O(n $log n$) < O($n^2$) < O($2^n$) < O(n!)

 

 

 

1.1.1. O(1) 상수

상수 시간이라고 말한다.

Array에서 index를 값으로 가져오는 것도 포함한다.

      

      

      

    
    

      <code />
    
public static void main(String[] args) {
    String[] arr = new String[3];
    int constant = 1;

    arr[1];
}

 

1.1.2. O(logN) 로그N

이진트리가 대표적

구현 코드 간단히 짜보자면 아래와 같다.

      

      

      

    
    

      <code />
    
public class TreeNode {
    private Object data;
    TreeNode left;
    TreeNode right;

    public TreeNode(Object data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    public Object getData() {
        return this.data;
    }
}

이런 이진트리로 어떤 탐색과정을 가지면 LogN 과정을 가진다.

 

1.1.3. O(n)

가장 일반적인 반복문 한번을 도는 시간복잡도이다.

      

      

      

    
    

      <code />
    
public static void main(String[] args) {
    // 100개 el이 있다고 가정
    int[] arr = new int[100];

    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }

    for (int[] el : arr) {
        System.out.println(el);
    }
}

 

1.1.4. O($n^2$)

가장 대표적인 구조는 이중반복문이다.

      

      

      

    
    

      <code />
    
public static void main(String[] args) {

    for (int i = 2; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
          System.out.println(i + j + " = " + i*j)
        }
    }
}

간단한 구구단인데, 반복문안에 반복문이 있다. 이 로직의 시간복잡도는 $n^2$ 이다.

 

1.1.5. 그 밖에

nlogN, n!, $n^n$ 등 다양하게 많지만 찾아보면 좋을듯 하다.