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

알고리즘을 공부하면 이해를 돕기 위한 그래프를 많이 볼 수 있다.

이 때 점근표기법으로 표현된 그래프를 많이 사용되는데 점근 표기법중 'big O(빅오)'에 대해 오늘 이해한 내용이다.

 

빅오 표기법은 알고리즘의 효율을 표현해주는 표기법으로 시간복잡도와 공간복잡도를 표현할 때 주로 사용된다.

---

1. big O 그래프 기본적인 해석방법

---

 

가로는 데이터양, 세로는 시간

 

위 그래프에서 빨강선 > 노랑선 > 초록선 순으로 비효율적이다.

어떤 알고리즘을 코드로 구현할 때 데이터양이 많아져도 시간이 오래걸리지 않는 방법을 생각해야한다.

 

이때 해당 알고리즘이 얼마만큼의 데이터에서 시간이 소요되는지 표현할 수 있다.

 

2. Big O 예제

---

예를 들어보자

 

① 첫번째 예시

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

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

 

이 때 시간복잡도와 공간복잡도를 이용한 big O로 표현하자면 아래 이미지와 같다.

 

가로는 데이터양, 세로는 시간

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

이것을 big O에서는 O(1)으로 표현한다.

 

② 두번째 예시

public void example(String[] arr) {
	for(String str : arr) {
    	System.out.println(str);
    }
}

위 코드에서는 배열 arr의 길이가 길수록 str을 출력하는 횟수도 증가한다.

가로는 데이터양, 세로는 시간

 

배열의 길이가 길면 찾는데 걸리는 시간은 배열의 길이만큼 step을 밟기 때문에 비례한다.

이것을 big O에서는 O(n)으로 표현한다.

 

③ 세번째 예시

public void example(String arr) {
   for(String str : arr) {
    	for(String str2 : arr) {
        	System.out.println(str + ", " + str2);
        }
    }
}

이중for문을 예시로 들어보자.

배열의 길이가 10인 경우 이중for문이기 때문에 총 100번의 step을 실행한다.

 

가로는 데이터양, 세로는 시간

배열의 길이가 길수록 거듭제곱된 steps를 실행하기 때문에 시간은 훨씬 오래걸린다.

이것을 big O에서는 O(n^2)으로 표현한다.

 

④ 네번째 예시

이진검색(Binary Search)을 big O 표기법으로 표현하겠다.

 

다음과 같이 오름차순으로 정렬된 배열이 있다.

{1,4,7,13,23,55,60}

여기서 23을 찾는 경우 이진검색으로 찾는 순서이다.

 

• 1. 배열의 길이의 중앙의 위치한 값을 먼저 찾는다.  = 13
• 2. 13과 찾는 숫자 23을 비교하면 23이더 크기 때문에 우측에 찾는 숫자가 있는 걸 유추할 수 있다.
• 3. 13을 포함한 좌측번호를 다 제거한 후 {23, 55, 60}만을 남긴다.
• 4. 또 반복해서 중앙의 위치한 값을 찾는다.
• 5. 55와 23을 비교하면 크기 때문에 좌측에 찾는 숫자가 있다는 걸 알 수 있다.

위 순서와 같이 이진검색은 log로도 표현할 수 있는데

컴퓨터가 프로그래밍을 통해 ( log 3 81 )이 공식을 풀기 위해서 4번의 step이 실행된다.

하지만 81의 2배인 162를 풀때도 답은 5이므로

 

big O 표기법으로 표현하면

 

가로는 데이터양, 세로는 시간

늘어나는 데이터 양의 비해 step은 비교적 적게 늘어나기 때문에 위와 같은 그래프가 되며,

big O로는 O(log N)으로 표현한다.

 

 

big O표기법을 알아두면 상황에 따라 효율 높은 알고리즘을 구현하기 위한 빠른 판단에 아주 큰 도움이 될 거다.