[Algorithm] 기본 수학 이론 - 알고리즘 복잡도

코딩테스트 할 때는 가장 중요시 여겨야 할 것 메모리 사용량, 효율성(시간 복잡도, 공간 복잡도) 이다.

 

시간 복잡도

• 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
• 3가지 점근적 표현법
  • O(빅오) : 최악의 상황을 고려하여 성능 측정 결과 표현
  • Θ(세타) : 평균적인 경우에서의 성능 측정 결과 표현
  • Ω(오메가) : 최선의 상황일 때의 성능 측정 결과 표현

아무래도 컴퓨터 프로그래밍쪽에서는 빅오 표기법이 널리 사용된다. 왜냐하면, 알고리즘의 평균적인 시간은 의미가 없는 경우가 많기 때문이다. 함수가 평균적으로 "대충 이정도 시간이 걸릴꺼야!" 보다 "절대로 이 시간 이상은 넘지 않을거야!" 라고 말하는 것이 신뢰도가 높고, 최악의 상황을 제일 고려해야 하는 것이 좋다.

 

Big-O Complexity Chart

 

빅오 표기법 예제

1

2

3

4