[TIL] 알고리즘의 시간 복잡도(Java)

✍ Today I Learned

 

시간 복잡도 표기법

• 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수
• 일반적으로 1억 번의 연산 = 1초의 시간으로 간주하여 예측
• 시간 복잡도를 정의하는 3가지 유형
  • 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 (1번)
  • 빅-세타 : 보통일 때(average case)의 연산 횟수를 나타낸  표기법 (2/n번)
  • 빅-오 : 최악 일 때(worst case)의 연산 횟수를 나타낸 표기법 (n번)
• 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 왜? 모든 테스트 케이스를 통과해야 하기 때문

 

 

시간 복잡도 활용

알고리즘 선택의 기준으로 사용하기

• 문제에서 주어진 시간제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단할 수 있다.
• 연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

 

[연습문제 000] 수 정렬하기 (백준 온라인 저지 2750번)

• 시간제한이 2초라면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.
• 문제와는 달리 데이터의 범위를 (1 ≤ N ≤ 1,000,000)로 가정하면 최대 크기는 1,000,000이다.
• 버블 정렬 = (1,000,000) ² = 1,000,000,000,000 ＜ 200,000,000 → 부적합 알고리즘
• 병합 정렬 = 1,000,000 log(1,000,000) = 약 2,000,000 ＜ 200,000,000 → 적합 알고리즘

 

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도 도축 기준은?

1. 상수는 시간 복잡도 계산에서 제외 (N이나 3N이나 차이 안남)
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준 (이중 for 문 하나가 굉장히 크리티컬함)

 

코드의 시간 복잡도를 도출할 수 있다면?

• 코딩 테스트에서 시간 초과가 발생했을 때, 문제가 되는 코드 부분 도출 가능!
• 연산에 더욱 효율적인 구조로 수정 가능!

 

 

 

 

※ 이 내용은 Do it! 알고리즘 코딩테스트 - 핵심이론 강의를 듣고 정리한 내용입니다.