[자료구조] #5 시간 복잡도

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

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

   ex) 정수의 절대값 계산 방법

      1) 제곱 후 루트 씌우기

      2) 음수일 때만, -1 곱하기

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

 

 

 

** 알고리즘 복잡도 계산 항목

1) 시간 복잡도: 알고리즘 실행 속도 ---> 반복문이 주요 결정 요소

2) 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

 

 

 

** 알고리즘 성능 표기법

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

 

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨

 

 

 

** 대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛^2), O(2^2), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)
      • 참고: log n 의 베이스는 2 - 𝑙𝑜𝑔2𝑛log2n
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다.
  • 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기한다.
  • n이 1이든 100이든, 1000이든, 10000이든 실행을
    • 무조건 2회(상수회) 실행: O(1)
    • n에 따라, n번, n + 10 번, 또는 3n + 10 번 실행: O(n)
    • n에 따라, 𝑛^2번, 𝑛^2 + 1000 번, 100𝑛^2 - 100, 또는 300𝑛^2 + 1번 실행: O(𝑛^2)
• 빅 오 입력값 표기 방법
  • 예: 
    • 만약 시간 복잡도 함수가 2𝑛^2 + 3n 이라면
      • 가장 높은 차수는 2𝑛^2
      • 상수는 실제 큰 영향이 없음 
      • 결국 빅 오 표기법으로는 O(𝑛^2)

 

 

 

 

** 실제 알고리즘을 예시로 이해

- 1부터 n까지의 합을 구하는 알고리즘

  1) 반복문 사용: O(n)

  2) 수학식 n(n + 1)/2 활용: O(1)

 

이와 같이, 동일한 문제를 푸는 알고리즘은 다양할 수 있음 어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해, 빅 오 표기법등의 시간복잡도 계산법을 사용함