[알고리즘] 기본 개념 정리 (1) - 시간 복잡도와 공간복잡도

이 시리즈는 고려대학교 정보대학 '유용재 교수님'의 수업을 듣고 정리한 자료입니다. 개인적으로 굉장히 존경하는 분이며, 더 알아보고 싶으신 분은 아래 링크를 참고해주세요.

 

https://yooy.mystrikingly.com/

 

---

시간복잡도, 공간복잡도

• 알고리즘
  • 주어진 문제를 해결하기 위한 단계적 절차 혹은 방법
  • 모호성이 없고 실행 가능하며 종결이 이루어지는 절차의 집합
• 시간복잡도
  • 어떤 프로그램이 소요하는 시간을 나타내는 개념
    • 시간복잡도(TC) = (컴파일 시간) c + (실행 시간) T(n)
    • 프로그램 분석에서 일반적으로 ‘실행 시간’이 ‘컴파일 시간’보다 중요
• 공간복잡도
  • 돌리는데 필요한 자원(리소스)
• 시간 > 공간 (중요성)
• ‘연산 횟수’가 중요
  • 반복이 아닌 단순 변수 선언 등은 무시
  • 실질적으로 나누거나 == 연산의 실행 횟수를 확인하면 됌

Big - O Notation

• 다음 명제가 참인 경우, T(n) = O(g(n))이라 나타낼 수 있음 모든 n≥n에 대하여, T(n) ≤ cg(n) 이 되게 하는 c와 n이 존재
• ‘최소한 너보단 연산이 더 적다’ = 점근적 표기
• 가장 중요한 항 이외에는 시간복잡도에서 무시됨
• 상수 하나 곱해졌다고 영향을 많이 못주니 → 그냥 핵심 부분만 빼낸다는 의미
• 정리 → ‘무한대로’ 보냈을 때 가장 영향이 큰 놈을 보면 됌.

(Big - O Notation 문제 보완)

• 오메가 → 반대 방향
• 세타 → O와 오메가의 샌드위치 시킴

빅 오 - 너 보다는 작다

오메가 - 너 보다는 많다

세타 - 너 사이에 있다

Bryte-Force

• 가능한 모든 경우의 수를 시도하여 맞추기 -> 시간이 소요되도 모든 경우를 확인하기에, 정확한 결과를 얻을 수 있다.