[CS/알고리즘] 빅 오 표기법

여태 그냥 O(N), O(N^2)이런거만 알았지 O가 무슨 의미인지 몰랐는데 오늘 수업을 통해 알게 되었다.

https://www.boostcourse.org/cs204

자바로 구현하고 배우는 자료구조

 

알고리즘 공부는 하고 싶고 어떤 강의를 들어야 좋을지 고민하던 중 부스트코스로 자바1을 다 듣고 자료구조 강의를 듣는 중이다.

 

이미지 출처 : https://www.boostcourse.org/cs204/lecture/480381/?isDesc=false

빅 오 표기법에서는 알고리즘 간의 관계를 다음과 같이 표현

- O (빅 오 복잡도) : 비교 대상인 다른 알고리즘과 같거나 더 빠르다.

- θ (세타 복잡도) : 비교 대상인 다른 알고리즘과 같다.

- Ω (빅 오메가 복잡도) : 비교 대상인 다른 알고리즘과 같거나 느리다.

- o (리틀 오 복잡도) : 비교 대상인 다른 알고리즘보다 더 빠르다.

- ω (리틀 오메가 복잡도) : 비교 대상인 다른 알고리즘보다 더 느리다.

 

리틀 오메가일때 가장 좋겠군 빅 오 표기법이 이런거에서 시작인거구나. 여태 너무 야매로 알고 있었다.