자료구조 B-tree 기본 개념 파악 (2)

저번 시간에 이어서 시간복잡도 개념을 아주아주 간단하게 개념만 익히는 포스팅을 하고자 한다.

 

처음에 이게 뭐 어쩌라고 싶은 내용이었는데 깊게 들어가면 어려운데 가볍게 이해하는 정도는 어렵지 않았다.

 

시간복잡도는 간단하게 말하면 알고리즘이 한번 도는데 걸리는 시간을 나타낸다!

 

예를 들면

오늘 하루의 계획이라는 알고리즘이 있다고 하자

 

오늘의 계획

1. 광화문에서 점심 약속

2. 합정에서 쇼핑하기

3. 강남에서 저녁 약속

4. 헬스장 가기

 

여기서! 각 지점에 어떻게 도달할 지는 사람마다 다를 것이다! 누구는 버스를 타고 누구는 택시를 타고 누구는 걸어서 혹은 지하철을 타고 혹은 환승하고 다양한 계획을 가지고 각각 다를 것인데 이렇게 진행하는 과정에서 걸리는 시간을 시간복잡도라고 이해하면 좋다.

 

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

 

최상의 경우는 신호도 안걸리고 너무나도 쾌적하게 이동했을 때 예상시간

평균은 일반적인 경우

최악은 신호마다 걸려버리고 환승시간도 길고 등등 여러모로 안좋을때의 예상시간

 

그럼 우리는 보통 평균을 잡지만 알고리즘에서는 최악의 경우에도 일정한 수준을 뽑아줘야하기 때문에 최악으로 판단하는 것이 좋다! 알고리즘은 복잡해서 최악의 경우 최상과 평균에 비해 시간이 너무나도 오래 걸리는 경우가 있기 때문

 

그래서 대부분 빅오 표기법을 사용한다고 하더라

 

앞선 포스팅과 연결해서 B-tree의 장점 중 하나가 이 시간복잡도다

 

최악의 경우에도 가장 빠른 logn의 속도를 보여주기 때문이다

 

복잡해져도 속도가 그리 느려지지 않는 O(log n)의 위엄

 

구체적인 내용은 더 깊게 공부해야하지만 난 일단 간단하게 이런 식으로 이해했다.