[자료구조] 빅오 표기법 Big - O notation에 대하여 알아보자. feat. JAVA 소스

알고리즘에 시간 복잡도 및 공간 복잡도를 표현하기 위하여 사용하는 표기법들이 있다.

이중 오늘은 Big - O에 대하여 이해하고 정리해보자.

 

절대적인 수행 시간을 따지게 된다면, 장비의 성능 및 그 컴퓨팅의 환경 또 작은 데이터에 대한 연산은 정확한 속도 값이라고 정의할 수 없다고 한다.

 

그래서 우리는 연산 횟수를 통하여, 얼마나 계산하는지 그것에 시간 복잡도와 공간 복잡도를 예측하여 표현하는데,

그 표현 방식 중에 하나인 Big - O 표기법에 대한 예제 및 설명이다. Big - O 표기법은 데이터가 증가하거나 , 추가될 때에 예측을 표현하는 방식이라고 한다.

 

위에 보시는 그래프는 http://bigocheatsheet.com/ 참조하여 인용하였다.

 

1. O(1) 

 

입력 데이터와 상관없이 일정하게 증가하는 알고리즘 시간과 요소와 일정하게 증가함. 위에 그래프를 참조해봐도 O(log n) , O(1)은 입력 데이터와 상관없이 시간이 따로 늘어나지 않음을 확인할 수 있다.

 

package myexample;


	public boolean getResult(int [] n) {
			return (n[0] == 0) ? true:false;
	}

 

2. O(n)

 

입력 데이터의 크기에 비례하여 입력시간도 같은 비율로 늘어나는 알고리즘 위 그래프와 참조하여 보면 이해하기가 더 쉽다.

 

public static void getResult(int [] n) {
		for(int i = 1; i <= n.length; i++) {
			System.out.print(i + " ");
		}
	}

 

3. O(n^2) 

 

입력 데이터 받은 n만큼 루프를 돌리는데, 그 안에서 루프를 또 n만큼 돌리게 될 때의 표기방법이다. n에 요소 하나당 n 만큼씩 늘어남으로 작은 양의 데이터일 땐 문제가 없지만 많아지면 많아질수록 위에 그래프와 같이 한 번에 수직 상승한다.

 

public static void getResult(int [] n) {
		for(int i=0; i<n.length; i++) {
			for(int j=0; j<n.length; j++) {
				System.out.print(i + j);
			}
		}
	}

 

4. O(nm) 

 

자바로 풀어낸 코드가 위에 O(n^2) 알고리즘과 비슷하다고 착각할 수 있으나,  이것은 m이 n보다 n > m  이런 상황이 있을 수 있으므로 다르다. 루프 모양만 보고 n^2 구나.. 하고 넘어가버리면 큰일 난다.

	public static void getResult(int [] n , int [] m) {
		for(int i=0; i<n.length; i++) {
			for(int j=0; j<m.length; j++) {
				System.out.print(i + j);
			}
		}
	}

 

5. O(n^3)

 

아래의 예제와 같이 같은 입력값을 3번 루프를 돌림으로써  n^2를 한 번 더 돌림으로써 늘어나는 값에 모양이 큐빅과 같은 구조를 뛴다. O(n^2)과 같은 그래프의 양상을 띄우지만, 훨씬 더 급격하게 증가한다.

	public static void getResult(int [] n) {
		for(int i=0; i<n.length; i++) {
			for(int j=0; j<n.length; j++) {
				for(int k=0; k<n.length; k++) {
					System.out.print(i + j + k);
				}
			}
		}
	}

 

6. O(2^n) 

 

얼핏 보면 n^2과 비슷할 수 있다고 착각할 수 있지만 너무나도 다른 알고리즘이다.

예를 들어 피보나치 수로 비유할 수 있다. 1 1 2 3 5 8 13... 이런 식으로 증가하는데 재귀 함수를 이용하게 되면 함수가 한번 호출 시 또 매번 2번씩 호출을 하게 됨으로써 트리구조 형태를 띄운다.  너무.. 정리를 막 했나 이해는 된다.!

 

      recursion(5)

       recursion(4)            recursion(3)

recursion(3) recursion(2)   recursion(2) recursion(1)

    ......   

  ..

위에 그래프에 n^3에 해당하는 것은 없지만 n^2 , n^3보다도  시간 복잡도가 훨씬 더 상승하는 것을 볼 수 있다.

 

7. O(m^n) 

 

O(2^n)에 2에 값을 m으로 바꾼다면,,? 그럼 m^n 만큼 늘어나는 양상을 띄울 것이다. 엄청나게 커진다. 위에 그래프에 나와있듯이..

	public static void getResult(int [] m , int [] n) {
		for(int i=m.length; i<=Math.pow(m.length , n.length); i++) {
			System.out.println(i + " ");
		}
	}
	

 

8. O(log n) 

 

대표적인 알고리즘으로는 이진 검색법이 되겠다 (binary search)

1,2,3,4,5,6,7,8 asc (오름차순)으로 정렬되어있는 어떤 배열 안에서 

어떠한 검색할 값이 주어졌을 때 예를 들어 = 5

중간값을 구해주면 

중간값 = 8 / 2  , 4

이제 남은 5 6 7 8중에서 찾아야 하는데 여기남은 데이터 중에 중간값을 또 구한다.

남은 배열에 길이 중간값 = 4 / 2 , 2가 되므로 5,6,7,8 중에

6이 선택된다 6보다 5가 작으므로 이제 현재 기준 뒤쪽 데이터는 볼 필요가 없어지므로 

6,7,8을 제외하고 나니

남은 데이터 5가 남는다.

이와 같이 위에 그래프를 참조하여보면 O(n) 보다도 O(log n)에 시간은 적다. 데이터가 증가하더라도, 시간이 크게 증가하지 않는다.

public class Ologn {
	public static int getResult(int k,int [] arr,int start,int end) {
		if(start > end) {
			return -1;
		}
		int mid = start+end/2;
		if(arr[mid] == k) {
			return mid;
		}else if(arr[mid] > k) {
			return getResult(k, arr, start, mid-1);
			
		}else {
			return getResult(k, arr,mid-1, end);
		}
		
	}
	
	
	public static void main(String[] args) {
		int [] arr = {1,2,3,4,5,6,7,8};
		System.out.print(arr[getResult(5, arr, 0, arr.length-1)]);
		
	}
}

 

7. O(Squered(n)) 제곱근

 

9 = 3  어떠한 입력값 n = 9라면  9 sqrt 3만큼 계산

16 = 4 어떠한 입력값이 n = 16라면 16 sqrt  4만큼 계산하는 방식이다.

 

 

 

 

대표되는 몇 가지의 알고리즘을 보고, 빅 오 표기에 대하여 정리해보았다.

 

그리고 명강의를 해주시는 분께서 빅 오 표기를 할 땐 Constant 상수를 버리라고 한다

 

예를 들어 O(2n)이라면 -> 2는 상수 고정된 값만큼 어차피 표현함으로 O(2n) 이어도 고정된 값은 신경 쓰지 않겠다 하여, 증가될 n에 대하여만 O(n)으로 표현한다고 한다.

 

O(n^2 + n^2) 도 위에 와 마찬가지로 O(n^2)으로 표현한다고 한다.