[Algorithm/Java] 시간 복잡도

• 시간 복잡도: 주어진 문제를 해결하기 위한 연산 횟수
• 1억번의 연산 → 1초로 간주

 

• 빅 오메가(Ω(n)): best case
• 빅 세타(θ(n)): average case
• 빅 오(O(n)): worst case → 코딩 테스트에서의 기준

 

• 버블 정렬: O(n^2)
• 병합 정렬: O(nlogn)

 

• 연산 횟수 = 시간 복잡도 * 데이터 크기

 

• 시간 복잡도 도출 기준
  • 상수는 시간 복잡도 계산에서 제외
  • 가장 많이 중첩된 반복문(이중 for 문이 있으면 그게 기준)의 수행 횟수가 시간 복잡도의 기준