[자료구조] 시간복잡도

자료구조 알고리즘을 학습하면서 동시에 고려해야 할 게 있다면 단연 시간 복잡도입니다. 

이번 시간에는 시간 복잡도와 Big-O표기법에 대해 간단히 정리하고자 합니다.

 

 

 

알고리즘이란?

알고리즘은 문제 해결 방법입니다. 

 

쉬운 예를 하나 들어보겠습니다. 눈앞에 5개의 공이 있고 각각 숫자가 써져 있습니다. 

누군가가 이 공들을 오름차순하고 싶은데 방법을 말해줄 수 있는지 물어보면 어떻게 대답하실 건가요?

 

우선 문제 상황과 해결 방법을 나눠서 정리해 볼 것 같습니다.

문제 상황 : 공 5개 오름차순 정렬
해결 방법 : 
  (1) 가장 작은 숫자를 찾아서 맨 앞에 놓는다.
  (2) 남은 공들에 대해서도 (1)의 방법을 반복한다.
  (3) 오름차순 완성!

이렇게 정리를 했을 때 '해결 방법' 부분이 알고리즘입니다.

 

 

 

 

지금은 공이 5개로 적지만 만약 공이 100개, 1,000개, 10,000개 이면 실행시간이 얼마나 걸리게 될까요?

공의 수가 많아져서 혹시 실행을 하다가 멈추게 되는 건 아닐까요?

 

이런 고민이 생길 수가 있습니다. 

 

 

 

따라서 알고리즘을 고안할 때는 미리 Running time*을 계산하고 접근해야 합니다. 

* Running time 실행시간

프로그램 시작부터 모든 코드를 처리하는 데까지의 시간

 

 

 

 

 

시간 복잡도

시간(T)과 입력값(input size, N)의 관계를 나타낸 것을 시간 복잡도라고 합니다.

 

 

알고리즘과 코딩 테스트를 공부할 때는 주로 Big-O표기법으로 표기하던데 그럼 Big-O표기법과 시간 복잡도는 다른 걸까요?

 

 

 

 Big-O표기법 (빅오표기법)

빅오 표기법은 복잡한 시간 복잡도를 간단히 표기하기 위해 최고 차수만 이용해 표기한 것을 말합니다.

Big -O는 시간 복잡도를 간단히 나타낼 수 있는 점근 표기법 중 하나로 시간 복잡도와 마찬가지로 가로축은 N, 세로축은 T을 나타내는 그래프로 표기할 수 있습니다.

 

점근 표기법이라는 것은 

예를 들어 T(n) = 1, T(n) = 260, T(n) = 530의 경우 N이 커질수록 차이는 미비하므로

상수의 시간 복잡도는  O(1)으로 점근 표기할 수 있습니다.

 

 

마찬가지로 1차 항은 O(n)으로 점근 표기할 수 있습니다.

 

 

이렇듯 입력값 N(input size)에 대한 실행시간 함수가 있다면 최고차 항의 계수만을 표기하여 Big-O n을 표기할 수 있습니다.

runtime(n)     Big-O

C = O(1)
an + b = O(N)
an² + bn + c = O(n²)

 

 

 

빅오 표기법을 그래프로 나타내 보겠습니다. 

그래프에 나와 있는 시간 복잡도의 성능을 비교해보자면, 오른쪽에서 왼쪽으로 갈수록 효율성이 떨어집니다. 

 

 

 

마지막으로 어떤 경우를 시간 복잡도로 쓸 것인가에 대해 알아보겠습니다.

시간 복잡도 Best case, Average case, Worst case

input size와 형태(예를 들어 역순)에 따라 시간 복잡도는 달라집니다.

 

우리가 말하는 알고리즘 시간 복잡도는Average case이지만, 구하기 까다로운 경우가 많습니다.

다행히도 Worst case는 Average case와 시간 복잡도가 같은 경우가 많기에 Worst case 통해서 알고리즘 시간 복잡도를 나타내기도 합니다. 

 

 

 

 

 

 

 

---

 

 

 

출처:

https://www.youtube.com/watch?v=GHClo7yu_20