알고리즘 복잡도

알고리즘 복잡도

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

가장 중요한 시간 복잡도를 이해하고 계산할 수 있어야 한다.

알고리즘 성능 표기법

• Big O 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법: Θ(N)
  • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

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

O 표기법

• 빅 오 표기법

• O(입력)

  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

• 표현식에 가장 큰 영향을 미치는 n의 단위로 표기

• n이 1이든100이든, 1000이든, 10000이든 실행 횟수에 따라 정의

  • 무조건 2회 (상수회) 실행 : O(1)

  if n > 10:
      print(n)

  • n에 따라 n번 , 3n +10번 등 실행 : O(n)

  for num in range(3):
      for index in range(n):
          print(index)

  • n에 따라 n^2번 , 300n^2 +1번 등 : O(n^2)

  for i in range(300):
      for num in range(n):
          for index in range(n):
              print(index)
  

시간 복잡도 예시

• 1부터 n까지 합을 구하는 알고리즘
  • 반복문 사용 없이 n 값에 따라 연산 가능
  • 시간 복잡도 : 1 , 빅 오 표기법 : O(1)

계산 복잡도

• 알고리즘의 계산 복잡도

  • 시간 복잡도 : 얼마나 빠르게 실행되는지
  • 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

• 두 가지 모두를 만족하기는 어렵다

  • 시간과 공간은 반비례적
  • 대용량 시스템이 보편화 되면서, 공간 복잡도보다는 시간 복잡도가 우선
  • 시간 복잡도가 중심

공간 복잡도

• 기존 알고리즘은 공간 복잡도도 고려해야할 때 만들어진 경우가 많다.
• 면접에서도 공간 복잡도를 묻는 경우가 있으므로 준비해두자.
• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양
  • 고정 공간 (알고리즘과 무관) : 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
  • S(P) = c + Sp(n)
    • c : 고정 공간
    • Sp(n) : 가변 공간빅 오 표기법을 생각해보면, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우 된다.

공간 복잡도 계산

• 알고리즘에서 사용되는 저장 공간을 계산

  • 빅 오 표현법으로 표현

• n! 구하기

  • n의 값에 상관없이 변수n, 변수 fac, 변수 index 만 필요
  • 공간 복잡도는 O(1)

  def factorial(n):
    fac = 1 
    for index in range(2, n+1): 
        fac = fac * index 
    return fac

• n! 구하기 2

  • 재귀함수를 사용했으므로, 변수 n이 n개가 만들어지게 된다.
  • factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 된다.
  • 공간 복잡도는 O(n)

  def factorial(n):
    if n > 1: 
        return n * factorial(n-1) 
    else: 
        return 1