0-1 시간 복잡도

📌참고 강의

https://www.inflearn.com/course/두잇-알고리즘-코딩테스트-파이썬#curriculum

---

📌시간 복잡도

✨ 시간 복잡도란 ?

• 시간 복잡도
  : 주어진 문제를 해결하기 위한 연산 횟수
• 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음.
  -> 이유 : 다양한 테스트 케이스를 수행해 모든 케이스를 통과 해야만 합격이므로 최악일 경우를 염두에 둬야 함.
• 데이터의 크기 (n) 가 늘어날수록 각 시간복잡도의 차이가 기하급수적으로 커짐.
  

✨ 시간 복잡도 유형

• 빅-오메가 (Ω(n)) : 최선일 때 (best case) 의 연산 횟수를 낱타낸 표기법
• 빅-세타 (Θ(n)) : 보통일 때 (average case) 의 연산 횟수를 나타낸 표기법
• 빅-오 (Ο(n)) : 최악일 때 (worst case) 의 연산 횟수를 나타낸 표기법

✨ 시간 복잡도 활용

• 백준 2750번 - 수 정렬하기
  -> https://www.acmicpc.net/problem/2750

💡 TIP 💡 

- 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n^2), O(nlogn) 이라고 알고 있다고 가정

- 최악의 경우를 생각할 것 !
-> 파이썬은 1초에 2천만 번 연산 가능
-> 2초가 주어졌으므로 4천만 번 이하의 연산 횟수로 문제를 해결해야 함.

• 연산 횟수 계산 방법
  : 연산 횟수 = 알고리즘 시간 복잡도 n 값에 데이터의 최대 크기를 대입하여 도출

• 알고리즘 적합성 평가
  

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