[암기용 요약] 점근 표기법(Big-O)

시간 복잡도

1. 알고리즘 수행시간 분석 결과
2. 단순히 증가하는 비율을 나타내는 개념
3. 수행시간이 어떻게 변화하는지 표현해주는 도구
4. 표기 예 : $O(logN), O(N), O(NlogN), O(N^2), O(2^N), O(N!)$
5. EX)

Q1. 위와 같은 가로 w, 세로 h의 울타리를 전부 칠하는데 드는 시간을 Big-O로 표현하면?

A1. O(wh)

Q2. p번 덧칠해야 한다면 Big-O는?

A2. O(whp)

• Big-O(오), Big-Θ(세타), Big-Ω(오메가)의 차이

1. Big-O : 시간의 상한(higher) 수행시간을 표현
2. Big-Θ : O, Ω 둘다 포함. 딱 맞는(exactly right) 수행시간을 표현
3. Big-Ω : 등가개념 혹은 하한(lower) 수행시간을 표현.

• 최선, 최악, 평균(많은 알고리즘이 최악과 평균이 같은 경우가 많음)

퀵정렬('축(pivot)'을 무작위로 선정해서 이보다 작은 값은 앞에, 큰 값은 뒤에 정렬하는 정렬기법)을 예로 들자면

1. 최선 : 모든 원소가 동일할 시 $O(N)$
2. 최악 : 가장 큰 원소가 계속해서 축이 될 경우 $O(N^2)$
3. 평균 : 최선과 최악의 평균 $O(NlogN)$

시간 복잡도 계산법

한마디로, 처리해야 할 데이터의수 n * 연산의 횟수(예제 및 연습문제를 참고해주세요)

Big-O의 순서는 아래와 같은데, 보통 $O(N^2)$이상의 복잡도를 가지는 알고리즘은 좋지 않다.

$O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)$

공간 복잡도

알고리즘의 메모리 사용량에 대한 분석결과

재귀호출 시 사용하는 스택 또한 '공간복잡도' 계산에 포함한다.

공간 복잡도 계산법

메모리를 얼마나 사용하는지 계산하면 된다.

표기 예 :

1. $O(n)$ : 크기가 n인 배열을 만들 수 있는 공간
2. $O(n^2)$ : n*n 크기의 2차원 배열을 만들 수 있는 공간

상수항은 무시하라

$O(2N)$ -> $O(N)$으로 표기

지배적이지 않은 항은 무시(제일 큰 경우의 수만 표기)

$O(N^2+N)$ -> $O(N^2)$으로 표기

$O(N+logN)$ -> $O(N)$으로 표기

$O(5*2^N+1000N^{100})$ -> $O(2^N)$으로 표기

$O(B^2+A)$ -> 하나의 항으로 표기할 수 없다.(A와 B의 특별한 관계를 알고 있지 않은 이상)

여러 부분으로 이루어진 알고리즘 : 덧셈 VS 곱셈

덧셈 : A작업을 끝낸 후 B작업을 끝낸다면 덧셈. $O(A+B)$

곱셈 : A작업을 할때 B작업을 같이하면 곱셈. $O(A*B)$

상환 시간

최악의 경우는 가끔 발생하지만, 한번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용(수행시간)을 분할상환 한다는 개념.

$logN$ 수행 시간

어떤 문제에서, 원소의 갯수가 절반 씩 줄어들때의 수행 시간.

이진트리(binary search)로 예를 들어보면,

이진트리는 N개의 정렬된 원소가 들어있는 배열을 반씩 줄여가며 검색값을 찾다가, 탐색해야 할 원소가 하나만 남으면 종료하는 특징이 있으므로

수행시간은 N을 절반씩 나누는 과정에서, 몇단계 만에 1이 되는지에 따라 결정된다.

N = 16일 경우,

N = 8

N = 4

N = 2

N = 1

인데, 순서를 뒤집어서 1에서 16으로 증가하는 것으로 생각해보면 수행횟수는 $2^k = 16$ 의 k이다.

이때 $2^k = 16$을 만족하는 k값을 구해주는 것이 바로 log.

$2^k = 16$

$log_216 = k$

$log_22^4 = k$

$4 = k$

따라서 이진탐색의 수행시간은

$2^k = N$

$log_2N= k$

로 구할 수 있고, 시간복잡도로 표현하면 $O(logN)$이 된다.

재귀적으로 수행 시간 구하기

재귀함수의 수행시간은 보통 $O(분기^{깊이})$로 표현된다.

(*분기(branch) : 재귀함수가 자신을 재호출하는 횟수)

예제 및 연습문제

(길어서 접어놓습니다)

예제1. 아래 코드의 시간 복잡도는?

답 : $O(N)$

for문 하나당 N, $O(N)+O(N) = O(2N)$ 인데, 상수는 무시하므로.

예제2. 아래 코드의 시간 복잡도는?

답 : $O(N^2)$

안쪽루프의 반복 횟수는 O(N)이고 이 루프가 N번 반복되므로.

예제3. 아래 코드의 시간 복잡도는?

답 : $O(N^2)$

여러 방법으로 구할 수 있지만, 평균을 이용한 방법으로 구해보면

array의 사이즈가 10일경우 안쪽루프의 경우 1,2,3,4,5,6,7,8,9,10.

평균값은 중간값으로 대략 5(Big-O에서는 정확하게 계산할 필요없음).

결국 1,2,3....N일 경우 평균값은 N/2이고, 안쪽루프 N/2가 바깥루프N번 수행되므로 $O(N*(N/2))$ -> $O(N^2)$

(+계속해서 업뎃합니다)

---

참고 사이트 : https://ledgku.tistory.com/33

이미지 출처 : http://rapapa.net/?p=3382

참고 문서 : 코딩 인터뷰 완전 분석 : 187가지 프로그래밍 문제와 해법