📚 시간 복잡도 & 공간 복잡도

• 시간복잡도(Time Complexity) : 알고리즘을 실행하는 데 걸리는 시간을 표현하는 방법
  즉, 내가 짠 코드의 실행 시간(Execution Time)을 예측해 얼마나 효율적인 코드인가를 나타내는 개념
  실행 시간은 연산(Operation)에 비례함.
  표현 방식 : 빅 오 표기법 (Big-O 표기법)
• 공간복잡도(Space Complexity) : 코드가 얼마나 메모리 공간을 효율적으로 사용하는지에 대한 개념
  컴퓨터 성능이 급격히 발달함에따라, 시간복잡도에비해 중요도가 보다 낮아짐.

📌Big-O 표기법😁

• 점근적 묘사 방법
• 알고리즘의 "효율성"을 평가하기 위한 분석법
• 시공간 복잡도를 수학적으로 표시하는 대표적인 방법
• 기본적으로, 최악의 경우 복잡도를 측정
• 단, 코드의 실제 러닝 타임을 표시하는 것이 아니라, 인풋 데이터 증가율에 따른 알고리즘의 성능을 (논리적으로) 예측하기 위해 사용.

• 2가지 규칙
  1. 가장 높은 차수만 남김(낮은 차수 항 무시​​) : O(n² + n) -> O(n²)
  2. 계수 및 상수는 과감하게 버림(계수 항 무시) : O(2n + 3) -> O(n)

• 시간복잡도 종류
• · O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
  · O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
  · O(n) – 선형 시간 : 문제를 해결하기 위한 입력 N 만큼의 단계가 필요.
  · O(n log n) - 선형 로그 시간 : 문제를 해결하기 위한 단계의 수가 N번에 그 하나의 N번당 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
  · O(n²) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
  · O(2ⁿ) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 2의 n 제곱.

• 시간복잡도 크기 순서
  O(1) < O(log n) < O(n) < O(n*log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
  

참고🔍

참고1
참고2
참고3