[D+51] 시간복잡도와 Big-o 표기법

 

D+51

-  시간 복잡도와 Big-o 표기법 -

(시간 복잡도와 Big-o 표기법)

 

---

 

 

시간 복잡도

알고리즘 문제를 해결하면서 시간이 얼마나 차지하는 지를 나타낸 것으로

이를 바탕으로 알고리즘의 성능을 수학적으로 표현해 준 표기법을 Big-o표기법이라고 한다.

 

Big-o 표기법

알고리즘의 성능을 수학적으로 표현해주는 기법으로 알고리즘의 시간과 공간 복잡도를 표현할 수 있다.

 

이때, 빅오표기법은 알고리즘의 실제 러닝타임을 표시하기보다는

데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것을 목표로 하기 때문에

상수와 같은 것들은 1로 바뀐다.

 

O(1)

입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다.

 

그래프처럼 데이터의 양과 상관없이 시간은 일정하게 같다는 것을 확인할 수 있다.

 

O(n)

입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘이다.

 

데이터의 양이 늘어날수록 시간도 비례하게 증가하는 것을 알 수 있다.

 

O(n2) n의 제곱

n개의 데이터를 받으면 첫 번째 루프에서 n번을 돌면서

각각의 엘리먼트에서 n번씩 또 돌아가는데 이는 n이 가로세로 면적만큼 돌아간다고 보면 된다.

 

초반에는 조금씩 상승하지만 나중에는 데이터를 조금만 추가해도 거의 수직 상승할 정도로 시간이 급증한다.

 

이처럼 데이터가 커질수록 처리시간의 부담이 커지는 것을 확인할 수 있다.

 

O(log n)

O(log n)은 대표적으로 BST(Binary Search Tree)가 있는데

원하는 노드 값을 찾을 때 루트를 시작으로 해당 값이 루트 값보다 작으면 왼쪽, 크면 오른쪽을 바라보게 된다.

 

이 과정에서 왼쪽이나 오른쪽 절반은 확인하지 않아도 된다.

 

이처럼 한번 처리가 진행될 때마다 검색해야 하는 데이터의 양이 절반씩 줄어들면서 소요시간이 점차 줄어든다.

 

O(n)과 비교해 보았을 때 훨씬 시간이 적게 든다는 것을 확인할 수 있다.