IM8일차 TIL ( Time complexity)

오늘은 그래프와 트리, 이진탐색트리 과제를 마무리 짓고 시간복잡도(time complexity)에 관해 공부하는 시간이었다.

 

시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수관계를 말한다.

 

시간복잡도는 기본적으로 Big-o 표기법을 사용한다.

 

O(n) , O(log n), O(n^2), O(C^n), O(n!) 등으로 나타낼 수 있다.

 

시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때,

 

알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 

 

위의 사진과 같이 O(1)이나 O(log n) 처럼 평평하게 나오는 곡선을 그리는 경우 문제 증가에 따라 걸리는 시간이 낮다고 할 수 있다.

 

반대로 O(n!)과 같이 위로 올라가는 곡선을 그리는 경우 문제가 조금만 증가 하더라도 걸리는 시간이 매우 오래 걸린다.

 

그래서 곡선이 완만한 시간복잡도를 가진 알고리즘을 이용하는 것이 중요하다.

 

시간복잡도의 특징으로 O(2n) 이나 O(n + 3) 이든 똑같은 O(n)의 복잡도를 가진다고 여긴다.

 

즉, 추가적인 수식은 제외하고 원래 형태로만 고려한다는 의미이다.

 

예를 들어 O(nlog n + 4)나 O(4n^2) 역시 각각 O(nlog n), O(n^2)로 표시해준다.

 

• 대문자 O 표기법
• 소문자 o 표기법
• 대문자 오메가(Ω) 표기법
• 소문자 오메가(ω) 표기법
• 대문자 세타(Θ) 표기법

시간복잡도는 5가지 표기법으로 표기할 수 있다.

 

---

배열(Array) 시간복잡도

배열의 시간복잡도는 각 배열의 요소를 접근할 때 O(1)의 복잡도를 가진다. 인덱스만 알고있으면 바로 접근 할 수 있기 때문이다.

 

배열의 요소를 찾을 때에는 각 인덱스를 하나하나 찾아야 하기 때문에 O(n)의 복잡도를 가진다.

 

마찬가지로 삭제와 추가를 할때에는 새로운 자리에 들어가거나 빈자리가 생기면 요소들이 밀리거나 당겨지기 떄문에 인덱스 변화로

 

O(n)의 복잡도를 가진다.

 

 

Linked list 시간복잡도

Linked list의 시간복잡도는 node에 접근하거나 찾기 위해서는 순서대로 움직여야 하기 때문에 O(n)의 복잡도를 가진다.

 

반대로 삽입이나 삭제를 할때에는 넣고 싶은 위치에 tail을 찾아서 연결만 하면되기 때문에 O(1)의 복잡도를 가진다.

 

 

Banary Search Tree 시간복잡도

BST 시간복잡도는 조금 독특하다.

 

찾고자 하는 값은 무조건 해당 root 보다 크거나 같기 때문에 나누어지고,

 

거기에서도 왼쪽, 오른쪽 나누어지면서 탐색되기 때문에 O(log n)의 복잡도를 가지게 된다.

 

다만, 한쪽 가지에만 값들이 몰려있는 구조로 나타나게 되면 최악으로 O(n)의 복잡도를 가지게 된다.

 

BST의 시간복잡도는 훌륭한 편이지만 이상 구조로 나타나는 경우 시간복잡도가 바뀔 수 있는 여지가 있다.

 

이런점 때문에 값이 한쪽으로 몰리지 않게 균형을 맞출 수 있도록 root를 조정해 줘서 BST를 구성하는 것이 좋다.