[기본] 시간복잡도 Time Complexity

## 알고리즘이란?

 

알고리즘 : 문제해결방법

예시 :

숫자가 적힌 5개의 공이 있다. 5개의 공을 오름차순 정렬을 하려고 한다. 어떤 방법으로 정렬을 완료할 수 있을까?

 

1/ 가장 작은 숫자가 적힌 공을 찾자 →  1

이 공을 맨 앞에 둔다. → 1  |  3  5  2  4

2/ 나머지 4개의 공(3 5 2 4) 중, 가장 작은 숫자가 적힌 공을 찾자 → 2

이 공을 두 번째 자리에 둔다. → 1  2  |  3  5  4

3/ 이 과정을 나머지 공들에도 반복하면 정렬이 완료된다.

 

 

정리해보면,

• 문제상황 : 공 5개를 오름차순 정렬
• 해결방법 : ' 알고리즘 '

1. 가장 작은 숫자를 찾아 서 맨 앞에 놓는다.
2. 남은 공들에 대해서 (1) 방법 반복

 

위 말로 풀어쓴 알고리즘을 코드로도 작성할 수 있다.

 

 

## 실행시간

이 알고리즘을 실행했을때, 시간이 얼마나 걸릴까?

또, 5개를 정렬할 때는 괜찮았는데, 공이 많아지면 너무 느려져서 사용할 순 없지 않을까?

그래서 알고리즘을 보완할 때는 실행시간을 미리 계산할 수 있어야한다.

 

우리가 작성한 코드를 컴퓨터에서 실행했을때 걸리는 시간을 실행시간(Running Time)이라고 한다.

프로그램을 실행하면 컴퓨터의 CPU가 코드를 한줄한줄 처리하게 된다.

이렇게 프로그램이 시작되는 시점부터 모든 코드를 처리하는데 걸리는 시간이 바로 running time.

 

 

반복문이 있는 코드도 한번 보자.

반복문의 실행시간은 반복 횟수를 곱해줘야한다.

(100번 반복되니 3ns x 100 = 300ns, 2ns x 100 = 200ns)

 

 

반복횟수가 10배 늘어나면 실행시간도 10배 늘어난다.

(10배 늘어나서 3ns x 100 x 10 = 3000ns, 2ns x 100 x 10 = 2000ns)

 

 

이번에는 반복문의 횟수가 n번이면 어떻게 될까? → 반복문이 5n의 시간이 걸린다.

(n배 늘어나므로 3ns x n = 3n ns, 2ns x n = 2n ns)

 

 

이중 반복문이면? → 5n의 시간이 걸리는 코드를 n번 반복하기 때문에 5n x n = 5n²

 

 

## 시간복잡도

이와 같이 시간과 입력값 n의 함수관계를 '시간복잡도'라고 한다.

복잡한 시간복잡도를 간단히 표기하기위해서 시간복잡도의 '최고차수'만을 이용해 Big-O 표기법을 쓸 수 있다.

 

Big-O는 시간복잡도를 간단히 나타낼 수 있는 '점근 표기법' 중 하나.
(**점근 표기법 : 'Big-O', 'Big-Omega', 'Big-Theta') 이렇게 3가지가 있다.

 

ex:

여기 530, 260, 1, n의 시간복잡도가 있다. 이걸 N에 대한 시간그래프로 나타내보자.

 

 

만약 시간복잡도가 n이라면, 그래프는 아래와 같이 나타난다. 

 

input사이즈 n이 커지면 커질수록 530, 260, 1의 차이는 미미해진다. 따라서 상수 시간복잡도는 O(1)으로 점근표기할 수 있다.

 

 

이번에는 시간복잡도가 5n+30을 N과 시간 t에 대한 그래프에 표시해보자.

N이 0일 때 → 실행시간 30, N이 1일 때 → 실행시간 35, .. 이렇게 5n +30의 그래프를 그릴 수 있다.

 

시간복잡도가 5n일 때, n일 때, n²일 때 그래프 모양은 다음과 같다.

 

 

n의 크기가 커지면 커질수록 n²과 n의 차이가 굉장히 커진다. 즉, 최고차항이 1차인 5n+30, 5n, n을 O(n)으로 점근 표기할 수 있다.

 

이처럼 입력값 n에 대한 실행시간 함수가 있다면, 최고차항에서 계수를 제외하여 Big-O(n)을 표기할 수 있다.

 

 

시간복잡도가 높은 순서는 다음과 같다.

 

## Best case, Average case, Worst case

처음에 언급했던 공 5개를 정렬하는 알고리즘은 다양하게 있다. → 선택정렬, 삽입정렬, 퀵정렬

이중에서 '삽입정렬'의 시간복잡도를 한번 구해보자.

코드를 얼핏보면 n번 반복하는 반복문이 2중 중첩되어있으니 시간복잡도가 O(n²)으로 정해진 것 같다.

 

하지만 입력값의 형태에 따라 매번 같은 횟수로 반복하지 않기 때문에 시간복잡도가 달라질 수 있다.

 

example:

입력값 크기가 5개로 동일하다 하더라도 (Input size=5), 공이 '35124'의 형태의 입력값일 때 정렬하기위한 시간복잡도와 입력값이 '52431'일 때는 시간복잡도가 달라진다.

 

'12345'로 이미 오름차순으로 정렬된 상태일 때는 반복문이 가장 적게 실행되어 시간복잡도가 가장 낮다.

'5,4,3,2,1' 이렇게 역순으로 정렬된 상태일 때는 반복문이 가장 많이 실행되어 시간복잡도가 가장 높다.

 

이번에는 공 10개, 즉 입력값의 크기가 10(Input Size = 10)일때도 한번 보자.

입력값의 형태에 따라서 시간복잡도가 달라진다.

0123456789일때는 시간복잡도가 가장 낮고, 역순일 때 시간복잡도가 가장 높다. 이렇게 입력값의 크기가 10으로 동일하더라도 입력값의 형태에 따라서 시간복잡도가 다양하게 나온다.

 

공이 15개일 때에도, 20개일 때에도, 25개일 때에도 시간복잡도는 다양하게 나온다.

 

이렇게 나온 시간복잡도에서 가장 높게 나온 시간복잡도 → Worst case

가장 낮게 나온 시간복잡도 → Best case

시간 복잡도의 평균값 → Average case

 

보통 알고리즘의 시간복잡도를 나타낼 때는 Average case를 말한다. 하지만 Average case는 구하기 어려운 경우가 많다. 다행히 Worst case와 Average case가 같은 경우가 많아 비교적 구하기 쉬운 Worst case를 구해서 알고리즘의 시간복잡도를 나타내기도 한다.

 

**출처 : 모든 내용은 인프런의 '코딩테스트 [ALL IN ONE]'강의를 기반으로 작성하였습니다.

https://inf.run/CSDT