[허언증/Algorithm] 시간복잡도 / 빅오표기법

시간복잡도

시간 복잡도란 big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타냅니다.

간단히 생각해서 프로그램이 총 몇번의 명령을 실행하는가? 입니다.

 

간단하게 예시를 두개를 가지고 이야기를 하도록 하겠습니다.

 

 

시작 값:1  / 종료 값:10

위 그림은 for문을 이용해서 구구단을 출력하는 프로그램입니다.

컴퓨터가 프로그램의 결과를 산출하기까지 총 11번을 실행하게됩니다.

 

소스코드

4,5 = 2번

7~8 = 9번

총 11번

빅오표기법으로 O(11) 입니다.

 

* 빅오표기법은 O(실행횟수)로 표시를 합니다

 

그 다음 소스코드를 확인해 볼까요?

 

시작 값:1  / 종료 값: n

같은 구구단을 출력하는 프로그램이지만,

이번엔 마지막수를 n으로 받았습니다.

고정적인 수가 아닌 n의 입력에 따라 숫자가 달라지며

명령어 횟수도 증가하게 됩니다.

 

소스코드

4,5 = 2번

7~8 = n번

총 n+2번

빅오표기법으로 O(n+2) 입니다.

 

두 번째 예시의 빅오표기법은 O(n+2) 맞지만 

사실상 상수 2는 의미가 없습니다.

n의 자리에서 숫자가 엄청큰 수 예를 들면 

n에 100000000000000000000 라는 숫자가 입력이 된다면

상수 2가 미치는 영향은 미미한 수준인걸 알 수 있습니다.

그래서 상수는 무시하고 O(n) 로 표기를 합니다.

 

상수 뿐만 아니라 O(n^2 + n)일 경우 

n이 n^2에 미치는 영향은 미미한 수준이기때문에 

O(n^2)라고 표기를 합니다.

 

 대표적으로

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

순으로 사용을 합니다

 

 

---

시간 복잡도를 따지는 이유는

 

프로그램마다 적용되는 알고리즘이 다르고 처리하는 양이 다 다르기때문에 

그 때 그 때 상황에 맞게 적합한 알고리즘을 사용하기 위함입니다.

문제은행에서 계속 풀다보면 아시게 되겠지만

 

 

 

1.선택,버블,삽입 => 빅오표기법 O(N^2)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

2.퀵,병합, 힙 => N(logN) 

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

실행 시간은 1초로 정해져 있지만 

빅오표기법 O(N^2)인 알고리즘으로 연산을 다 못 하고 

더 빠른 알고리즘인 N(logN) 를 사용하면 1초안에 연산을 완료할 수 있기 때문입니다.