Algorithm 3 시간 복잡도

알고리즘 복잡도 표현 방법

1. 알고리즘 복잡도 계산이 필요한 이유

1.1 하나의 문제를 푸는 알고리즘은 다양할 수 있음

• 정수의 절대값 구하기
  • 1, -1 → 1
  • 방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기
  • 방법2 : 정숙 ㅏ음수인지 확인해서, 음수일 때만, -1을 곱하기

    다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

2. 알고리즘 복잡도 계산 항목

• 시간 복잡도 : 알고리즘 실행 속도 → 반복문이 지배
• 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

3. 알고리즘 성능 표기법

• Big O(빅-오)표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
• $\Omega$(오메가)표기법 : $\Omega$(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• $\theta$(세타)표기법 : $\theta$(N)
  • 세타 포기법은 알고리즘 평균실행 시간을 표기

4. 대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O($log n$), O(n), O(n$log n$), O($n^2$), O($2^n$), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O($log n$) < O(n) < O(n$log n$) < O($n^2$) < O($2^n$) < O(n!)
      • 참고: log n 의 베이스는 2 - $log_2 n$