시간복잡도(Time Complexity), 공간복잡도(Space Complexity) 간단하게 이해하기.

실력있는 개발자가 되기위해 필수로 이해하고 있어야하는 알고리즘 성능을 판단하는 두 가지 복잡도에 대해 포스팅하겠다.

 

성능이 좋은 알고리즘이란?

 - 실행하는데 걸리는 시간이 짧아야하고, 그 과정에서 메모리같은 자원을 가능한 적게 사용하는 것이 효율적이라고 할 수 있다.

( 하드웨어 성능이 좋아지면서 공간복잡도는 크게 중요하지 않다. 게다가 시간복잡도와 공간복잡도는 반비례적이어서 효율적인 알고리즘은 시간 복잡도를 위주로 판단한다. )

 

시간복잡도(Time Complexity)

 - 시간 복잡도는 알고리즘의 연산 횟수이다.

① 연산을 측정하는 방법

 - 예시.

public void example(String[] arr) {
	Syatem.out.println(arr[0]);
}

example 함수의 파라미터 배열 arr의 사이즈의 관계없이 arr[0]은 한번만 실행된다.

배열의 0번째 저장된 데이터만 불러오기 때문에 배열의 길이가 길어도 찾는데 걸리는 시간은 같다.

빅오표기법으로 O(1)이다.

 

공간복잡도(Space Complexity)

 - 공간 복잡도는 '고정 공간'과 '가변 공간'이 있다.

① 고정 공간은 입ㆍ출력과 관계없는 공간을 말한다.

  - 예시 : 단순변수, 상수변수 등

public void example() {
    int people = 1;
    int employee = 1;
}

   - 위 코드블럭과 같은 경우의 공간복잡도는 빅오표기법으로 O(1)이다. 이유는 변수의 할당이 고정적이기 때문이다.

 

② 가변 공간은 동적인 공간을 말한다.

  - 예시 : 비즈니스 로직에서 특정 인스턴스의 반복적인 할당 등

public void example(int n) {
    LinkedList<Integer> linkedList = new LinkedList<>();
    
    for(int i=0; i<n; i++) {
    	linkedList.add(i);
    }
}

 - 위 코드블럭과 같은 경우의 공간복잡도는 빅오표기법으로 O(n)이다. 이유는 변수의 할당이 n만큼 스택에 쌓이기 때문이다.

 

빅오 표기법(Big-O)

 - 시간복잡도와 공간복잡도와 관련되서 이어서 익혀야되는 내용이 빅오 표기법이다.

   해당 내용은 아래 URL에서 확인하자.

https://jfbta.tistory.com/77

점근 표기법 - big O(빅오 표기법) 쉽게 이해하기