시간 복잡도(Time Complexity)와 빅오(Big O) 표기법에 대해 알아보쟈!

알고리즘 첫 포스팅이다.
무엇을 할까 고민하다가 
요즘 엄청난 문제상황에 처했다.

아니 뭐냐규 이거 어떻게 해결해야함....

문제 풀때마다 시간초과 오류발생.... 

검색하다보니 시간복잡도라는게 있더랬다 

 

좋은 알고리즘은 무엇일까? -> 빠르고 효율적이다

어떻게 측정할 수 있지?

이때 참고할 수 있는게 '복잡도'개념이다.

 

복잡도에는 시간복잡도(Time complexity) , 공간 복잡도( Space complexity)가 있다. 

시간 복잡도 - 알고리즘의 계산시간 측정

공간 복잡도 - 알고리즘의 메모리 사용량 측정 

 

- 시간복잡도를 어떻게 표기할 수 있을까?

 표기법에는 3가지가 있다.

- 란다우 빅오 표기법 (Big O) 

- 오메가 표기법

- 세타 표기법

 

대중적으로 란다우 빅오 표기법을 널리 사용하므로 란다우 빅오 표기법에 대해 자세히 알아보자

 

- 란다우 빅오 표기법 (Big O) 

 

T(N) = 알고리즘의 계산시간 

P(N) =>  (N,

알고리즘 A의 T(N)이 대략적으로 P(N)에 비례하면

T(N) = O(P(N))이라고 표기하고 알고리즘 A의 복잡도는 O(P(N))이라고 부른다.

 

예)

알고리즘 A의 계산시간 T(N)이  다음과 같다면

아래 수식으로 표현할 수 있다.

T(N)은 대략 n²에 비례한다고 할 수 있다.

T(N) = O(N²) 이라고 나타내고 이 알고리즘의 복잡도는 O(N²)이라고 부른다.

 

# 최고차항 이외를 제외해도 되는 이유는?

- N이 커질수록 N²(최고차항)은 압도적으로 커진다. 

# 계수를 생략해도 되는 이유는?

- 실제 정확한 계산시간을 확인해야 한다면 계수를 고려해야야겠지만 대략적인 측정단계라면 무시해도 됨 

N이 매우 크다면 다음 N³(다음 차수항)은 3N²(최고차항) 보다 훨씬 크기 때문 

 

 

오른쪽으로 갈수록 느려진다

 

- 그렇다면 알고리즘은 어떻게 짜야하는가?

컴퓨터의 연산속도 = 1초에 대략 1억번 연산

O(N) => N=1억 까지 1초

O(N²) => N=1만 까지 1초

 

만약 문제에서 시간제한이 1초라면 

즉, 알고리즘의 시간복잡도가 O(N) 일 경우 문제 해결을 위해 연산을 1억번이내에 마쳐야 하며 O(N²)일 경우 1만번 이내에 연산을 마쳐야 한다

 

# 1초 내 입력크기 (대략 컴퓨터가 1초 1억번 연산 가능하다고 가정)

- O(1)

- O(logN), O(N) : 1억

- O(NlogN): 5백만

- O(N^2) : 1만

- O(N^3) : 500

- O(2^N) : 20
- O(N!): 10

-> 대략적으로 시간제한과 입력 크기 판단하면서 알고리즘 구성하기!!