Data Structure - 알고리즘 시간복잡도

알고리즘 복잡도

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

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
  • 시간 복잡도: 얼마나 빠르게 실행되는지
  • 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘

• 통상 둘 다를 만족시키기는 어려움
  • 시간과 공간은 반비례적 경향이 있음
  • 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
  • 그래서! 알고리즘은 시간 복잡도가 중심

알고리즘 시간복잡도의 주요요소

• 반복문이 시간복잡도를 control

알고리즘 성능 표기법

• Big O (빅-오) 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기법
  • 아무리 최악의 상황이라도, 이 정도의 성능은 보장한다는 의미
  • O(입력)
    • 입력 n에따라 결정되는 시간복잡도 함수
    • 참고로 O(logn) 에서 로그의 밑은 2 (10이 아님)

시간복잡도 구하기

1. 1부터 n까지의 합구하기 알고리즘 (1)

   int sumNumber ( int n)
   {
    int sum = 0;
    for (int i = 0; i <n ; ++i)
    {
        sum += i;
    }
   }
   

   • 시간복잡도
   • 입력 n 에 따라 덧셈을 n 번 반복 (반복문)
   • O(n)
2. 1부터 n까지의 합구하기 알고리즘 (2)

   int sumNumber (int n)
   {
    int sum = (n*(n+1)) / 2;
   }
   

   • 시간복잡도
   • 입력 n이 어떻든간에 연산을 하면됨 (반복문 없음)
   • O(1)

공간복잡도 구하기

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
    • $ S(P) = c + S_p(n) $
    • c: 고정 공간
    • $ S_p(n) $: 가변 공간

빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우됨

• 상수: 입력값과 상관없으니까 상수라고 표현 – 즉 고정공간은 입력값과 비례하여 차지되는 공간이 아니므로 상수취급함

1. n! 팩토리얼 구하기
   • n! = 1 x 2 x … x n
   • n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
   • 공간 복잡도는 O(1)

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

2. n! 팩토리얼 구하기
   • n! = 1 x 2 x … x n
   • 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
     • factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
   • 공간 복잡도는 O(n)

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