[TIL - Codesquad] 빅 오 표기법

[20.01.12]

오늘은 미션 제출하느라 코딩을 많이 해서 공부는 많이 하지 못했다.

그룹원들이 추천한 빅오표기법에 대한 영상을 보고 정리하는 것으로 마무리하기로 했다. 

---

TIL

빅 오 표기법

 www.youtube.com/watch?v=6Iq5iMCVsXA&feature=youtu.be

 

복잡도 Complexity 분석

- 성능 측정을 위한 방법 중 하나.
- 공간복잡도와 시간복잡도 분석을 가장 많이 활용.

빅 오 표기법 Big-O notation

- 알고리즘의 성능을 수학적으로 표현해 주는 표기법.
- 빅오표기법으로 알고리즘의 시간복잡도와 공간복잡도를 표현할 수 있다.
- 알고리즘의 실제 running time을 표시하는 것이라기보다, 
데이터 / 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표임. 
( -> Drop Constant : 상수와 같은 숫자들은 모두 1이 됨 - 맨 끝에서 다시 설명. )

---

아래는 기본적인 빅 오 표기법의 예시들이다.

1. O(1) 알고리즘 : constant time 상수 시간

: 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.

O(1)알고리즘 예시 코드

int function(int[] numArr) {
  return (numArr[0] == 0) ? true : false;
}
-> 매개변수인 numArr이 아무리 커도 일정한 속도로 결과를 반환함.

O(1)알고리즘 그래프

(x축 : 데이터의 크기 data, y축 : 처리시간 time)

: 데이터가 아무리 증가해도 처리시간이 일정하다. 즉, 성능에 변함이 없다.

 

2. O(n) 알고리즘 : liner time (선형 시간)

: 입력 데이터의 크기에 비례하여 처리시간이 증가하는 알고리즘.

O(n) 알고리즘 예시 코드 

void function(int[] numArr) {
  for (int i = 0; i < numArr.length; i++ {
    System.out.println(i);
  }
}
-> numArr 배열의 길이가 n이라면 for문도 n번을 반복하게 된다. 
n이 하나 커질 떄마다 for문의 반복횟수도 n번 증가한다.
즉, n의 증가율만큼 처리시간도 증가한다.

O(n) 알고리즘 그래프

: 데이터가 증가함에 따라 처리시간도 비례해서 증가한다.
( 데이터의 증가율 = 처리시간 증가율 -> 그래프는 언제나 직선으로 표현된다)

 

3. O(n^2) 알고리즘 : (오 엔 스퀘어)

O(n^2) 알고리즘 예시 코드

void function(int[] n) {
  for (int i = 0; i < n.length; i++) {
    for (int j = 0; j < n.length; j++) {
      System.out.println(i + j);
    } 
  }
}
-> 위와 같은 이중루프 코드일 때 O(n^2)이 된다.

n개의 데이터를 받으면 그 데이터마다 반복문을 실행하고, 각 데이터 내에서도 반복문을 실행하므로
실행해야 하는 횟수는 위의 그림처럼 n^2 회가 된다.
데이터가 커질수록 처리시간의 부담이 커진다.

O(n^2) 알고리즘 그래프

-> 처음에는 조금씩 상승하다가, 데이터가 커질수록 처리시간이 제곱으로 증가해 그래프가 수직에 가까워진다. (곡선형)

 

4. O(nm) 알고리즘 (오 엔 엠)

O(nm) 알고리즘 예시 코드

void function(int[] n, int[] m) {
  for (int i = 0; i < n.length; i++) {
    for (int j = 0; j < m.length; j++) {
      System.out.println( i + j );
    }
  }
}
-> 같은 이중루프문이라 O(n^2)와 비슷해 보이지만,
numArr1을 두 번 돌리는 게 아니라 numArr1을 numArr2만큼 돌리는 것이다. (헷갈리지 않게 주의)

-> n을 m만큼 반복하게 되므로 위 그림처럼 n*m이 된다.
n은 아주 큰 수, m은 작은 수 일 수도 있다.

O(nm)의 그래프

-> O(n^2)와 마찬가지로 데이터가 증가하수록 그래프가 수직에 가까워진다 (곡선형).

 

5. O(n^3) 알고리즘 : polynomial time / cubic time (다항 시간)

O(n^3) 예시 코드

void function(int[] n) {
  for (int i = 0; i < n.length; i++) {
    for (int j = 0; j < n.length; j++) {
      for (int k = 0; < k.length; k++) {
        System.out.println(i + j + k);
      } 
    }
  }
}
-> 삼중루프문. n을 세 번 반복해서 돌린 경우 n의 세제곱이 된다.

-> O(n)은 직선, O(n^2)는 면적, O(n^3)은 부피 = 큐브 가 된다.

O(n^3) 그래프

-> O(n^2)와 비슷한 곡선형이지만, 세제곱이므로 기울기가 더 급격하게 수직에 가까워진다 (곡선형).
데이터 증가에 따라 처리시간이 더욱 급격하게 증가한다.

 

6. O(2^n) 알고리즘 : exponential time 지수 시간

피보나치 수열 - 1부처 시작해 한 면을 기준으로 정사각형을 만들어 붙인다. 그 다음 긴 면 기준으로 정사각형을 기준으로 붙인다. 반복한다. (1 - 1 - 2 - 3 - 5 - 8 ...)

피보나치 수열.
앞의 수 두 개를 더해 뒤의 수를 만든다.
1, 1, 2, 3, 5, 8..

O(2^n) 알고리즘의 예시 코드

재귀를 활용해 피보나치 수열을 구하는 코드가 O(2^n)알고리즘에 해당한다.
-> 이전 숫자와 전전 숫자를 알아야 둘을 더해 다음 숫자를 얻을 수 있기 때문에, 매번 함수를 호출할 때마다 두 번씩 더 호출하게 된다.

-> 매번 함수를 호출할 때 마다 두 번씩 더 호출하게 되는데, 그것을 트리의 높이 (k) 만큼 반복한다.

O(2^n) 그래프

-> O(n^2), O(n^3)보다도 급격하게 그래프가 수직에 가까워진다(곡선형).
데이터 증가에 따라 처리시간이 가장 급격하게 늘어난다.

 

6-1. O(m^n) 알고리즘 - 지수 시간

위의 O(2^n)알고리즘이 2개씩 n번 늘어나는 것과 비슷하게,
O(m^n)은 m개씩 n번 늘어나는 알고리즘이다.

7. O(log n) 알고리즘 

O(log n) 알고리즘 예시 코드

- 이진검색 binary search 코드가 O(log n)알고리즘의 대표적인 코드이다.
매번 찾는 데이터가 중간값보다 큰지/작은지 비교하여 검색대상을 줄여나감.
-> 한 번 처리가 진행될 때 마다 검색해야 하는 데이터의 양이 절반씩 줄어듦 -  O(log n)알고리즘이라고 함.

O(log n) 알고리즘 그래프

-> 데이터가 증가해도 성능이 크게 차이나지 않는다.

 

8. O(sqrt(n)) 알고리즘 - 오 스퀘어 루트 n

sqare root = 스퀘어 루트 = 제곱근.

3 * 3 = 9 이므로 9의 제곱근은 3이 된다.

 

어떤 수 n을 정사각형 속에 채우면, 그 정사각형의 한 변이 제곱근이 된다.

 

Drop Constants 상수 버림 (상수 무시)

- 빅오 표기법에서 꼭 알아두어야 할 개념.
- 빅오 표기법에서 상수는 과감하게 버린다. 즉, 어떤 상수는 1로 취급한다.

예를 들어,

void function(int[] n) { 
	for (int i = 0; i < n.length; i++) { 
		System.out.println(i); 	
	}
	for (int i = 0; i < n.length; i++) { 
	System.out.println(i);
	}
}

void function(int[] n) {
	for (int i = 0; i < n.length; i++) {
    	for (int j = 0; j < n.length; j++) {
        	System.out.println(i + j);
        }
    }
    for (int i = 0; i < n.length; i++) {
    	for (int j = 0; j < n.length; j++) {
        	System.out.println(i + j);
        }
    }
}

1번 코드블럭은 n을 두 번 돌리니까 실제로는 O(2n)의 시간이 걸린다.
2번 코드블럭은 이중루프를 두 번 반복하므로 실제로는 O(n^2+n^2) = O(2n^2)의 시간이 걸린다.
하지만 빅오 표기법으로는 두 경우 모두 2라는 상수를 없애버리고, 각각 O(n), O(n^2)라고만 표시한다.

Why? 빅오 표기법은 실제 알고리즘의 running time(실행시간)을 재기 위한 것이 아니라,
장기적으로 데이터 증가에 따른 처리시간의 증가율을 예측하기 위해 만든 표기법이기 떄문.

상수는 고정된 숫자이므로, 증가율에 영향을 미칠 때도 고정된 상수만큼만 영향을 미친다.
빅오표기법은 증가하지 않는 숫자 (고정된 숫자=상수)는 신경쓰지 않는다.
그렇기 때문에 상수를 무시하는 것.

 

---

** 내일 할 일 **

알고리즘 미션을 열심히 풀고 제출하기.

단일 연결 리스트, 이중 연결 리스트, 선형 리스트, 환형 리스트의 특성과 활용하는 경우.

Big-O 표기법과 같은 복잡도 분석 학습하고 정리한다. *

Queue와 Deque에 대해 학습 및 링크드리스트로 구현방안 설계.

+ 호눅스가 추천해 준 마크다운 툴 Typora를 활용해서 TIL을 적어보자! 마크다운 언어에 익숙해져야 한다.