오늘 알아볼 내용은
1. 시간 복잡도, 공간 복잡도 정의
2. Big-O Notation

💡시간 복잡도

➡ 정의

• 알고리즘을 프로그램으로 실행해 완료하는 데까지 소요되는 시간
• 시간 복잡도 = 프로그램 컴파일 시간 + 실행 시간
  • 컴파일 시간은 프로그램 특성과 큰 관련 없음 → 고려 안해도 된다
  • 실행 시간도 컴퓨터에 따라 성능이 달라질 수 있기에 명령문의 실행 빈도수를 계산해 추정
  • 진짜 실행 시간으로 비교하고 싶다면 서로 다른 알고리즘을 동일한 hardware에서 실행시켜야 함

➡ 분석 방법

• 입력 크기 n에 대한 실행 시간의 증가율만 분석하는 점근적 분석(Asymptotic Analysis)을 활용
  • 증가율만 보기에 실행 빈도 함수의 상수항과 계수 무시하고 가장 큰 하나의 항에 대해서 차수 표기법(Order Notation)으로 시간 복잡도를 표기
  • 무시하는 이유 : 정확한 연산의 개수를 알고 싶은게 아니라 input n에 따른 증가 추세가 궁금하기 때문에 n이 커질수록 상수항과 계수의 영향력은 미미해진다

➡ 표기 종류

1. Big-O notation (하한)
   • 최악의 경우에도 g(n) 안에는 수행
2. Big-Omega notation (상한)
   • 최소 g(n)의 수행 시간 필요
3. Big-Theta notation (정확)
   • 상한과 하한이 같은 정확한 차수를 표기하기 위한 표기법
   • 정확한 시간복잡도 계산이 가능할 때 사용 → 어려움 → 빅오사용

💡공간 복잡도

➡ 정의

• 프로그램 실행과 완료까지 얼마나 많은 공간(메모리)가 필요한지
• 총 필요 공간 = 고정 공간 + 가변 공간
  • 고정 공간
    • 입출력 횟수, 크기와 관계없는 공간들을 말함(코드 저장 공간, 단순 변수, 상수 등)
    • int, double, 크기가 정해진 배열
    • 상수 → 성능에 큰 영향 X
  • 가변 공간
    • 필요에 따라 동적으로 할당, 해제되는 메모리 공간
    • 특정 instance에 따라서 사이즈가 달라지는 변수들
    • 성능에 큰 영향 O
• 통상적으로 시간 복잡도와 공간 복잡도는 반비례적인 경향이 있음
  • 최근은 하드웨어가 대용량에다가 가격도 싸졌기에 공간 복잡도보다는 시간 복잡도가 우선

➡ 표기 방법

• 시간 복잡도와 마찬가지로 Big-O 표기법 사용한다

💡Big-O Notation

➡ 정의

• 실행 빈도 함수의 상한을 나타내기 위한 표기법
• 최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘이 수행이 완료된다
• 일반적으로 최악의 경우를 고려한 해결책을 찾기에 Big-O를 주로 사용한다

➡ 실행 시간 함수 (오름차순)

1. $O(1)$
2. $O(log N)$
3. $O(N)$
4. $O(Nlog N)$
5. $O(N^2)$
6. $O(N^3)$
7. $O(2^N)$

• 1번이 제일 빠르고 갈수록 점점 느려짐