시간복잡도

👾 시간 복잡도

주어진 문제를 해결하기 위한 연산 횟수
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측
→ 시간 제한이 2초이면 2억 번의 연산 안에 답이 나와야 한다.

🔍 시간 복잡도가 중요한 이유? 알고리즘 선택의 기준이 되기 때문!
본인이 짠 코드가 시간 복잡도가 과연 몇인지,
얼마나 효율적으로 짰는지 따져볼 수 있어야 한다.

👾 시간 복잡도 유형

• 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법 (1번)
• 빅-세타: 보통일 때(average case)의 연산 횟수를 나타낸 표기법 (N/2번)
• 빅-오: 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 (N번)
  ⭐ 실제 코딩 테스트에서는 빅-오 표기법을 기준으로!
       테스트 셋이 단순하게 나오지 않고, 시간 복잡도 내에서 정답도 맞아야 하기 때문에
       항상 가장 최악의 케이스를 염두하고 코딩 테스트에 임해야 한다.

👾 연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

• 시간 복잡도 도출 기준
  1) 상수는 시간 복잡도 계산에서 제외한다.
  2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

예) 버블 정렬 연산 횟수: 1,000,000,000,000회 ← 부적합 알고리즘
     병합 졍렬 연산 횟수: 20,000,000회 ← 적합 알고리즘