[자료구조/알고리즘] 알고리즘 복잡도 표현방법

알고리즘 문제를 풀어보면서, 차근차근 test 해보자!

알고리즘 복잡도 표현방법

하나의 문제를 해결하는데 알고리즘은 엄청 다양하다. 그 알고리즘들을 분석
다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석/ 복잡도를 정의하고 계산

알고리즘 복잡도
1)시간 복잡도: 실행속도 측정
2)공간 복잡도: 메모리 사이즈 측정

시간복잡도의 주요요소
반복문이 지배한다.
우선 반복문을 어떻게 쓰는지에 따라 시간복잡도에 영향을 준다. 가장 크게 준다 등으로 이해하자.

성능 표기법

• Big O(빅-오) 표기법
  * 알고리즘 최악의 실행 시간을 표기.

  • 가장 일반적으로 사용!
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미

• 오메가 표기법
  * 오메가 표기법은 알고리즘 최상의 실행시간을 표기

• 세타 표기법
  * 알고리즘 평균 실행 시간을 표기

• O(1) < O(logn) < O(n) < O(nlogn) < O($n^2$) < O($2^n$) < O(n!)