시간 복잡도

시간 복잡도

시간복잡도란 알고리즘의 성능, 즉 연산 횟수를 측정하는 것을 의미하며 시간복잡도가 낮을수록 효율적이라고 볼 수 있다.

빅 오 표기법

자료구조와 알고리즘의 효율성을 분류해 놓은 기법을 의미한다.

빅 오의 본질은 데이터의 양이 늘어났을 때 알고리즘의 성능이 어떻게 변하는지를 뜻한다.

코딩테스트에서 빅 오 표기법 활용 방법

코딩테스트에서는 입력 값이 제한시간안에 출력이 되는지를 보는 것. 연산 횟수는 1000 ~ 3000만 정도로 고려할 것!

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3000 ~ 5000
O(NlogN)	100만
O(N)	1000 ~ 2000만
O(logN)	10억

 

배열에서 7이라는 숫자를 찾을 때, 한개 한개 첫번째 index부터 찾아가게 되는데 그럼 언제 값을 빨리 찾을까요?

1차원 배열을 생각해보면 당연히 인덱스가 앞에 부분에 있을 때 빨리 찾겠죠. 

이러한 방식은 시간복잡도가 O(N) 입니다. 쉬운 문제도 처음에는 시간복잡도를 따지는 연습을 하자!

1

2

3

4

5

6

7

8

9

시간 복잡도 계산하기

시간복잡도는 데이터 갯수 N에 대해 f(x) = x^2 + 3x + 5 와 같이 계산해주고 최고차항을 빼고 지워주면 됩니다. 

즉, 시간복잡도는 O(X^2)

 

별 찍기 문제

N = 3              N = 5

*.                     *

**                    **

***                  ***

                       ****

                       *****

f(N) = 1 + 2 + 3 + .... + N = N(N+1) / 2 = O(N^2)

 

개미 수명 문제

16 -> 8 -> 4 -> 2 -> 1 -> 0

N  -> (1/2)^1N -> (1/2)^2N -> (1/2)^3N -> (1/2)^YN

이런 순서대로 수명이 준다고 했을 때 N년 후 개미 수명은  (1/2)^Y N = log2N  = O(log2N)