[알고리즘] 시간 복잡도

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다.

시간 복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다. 일반적으로 1초에 1억번의 연산을 할 수 있다.

문제에서 시간 제한이 2초라면, 2억 번 이하의 연산 횟수로 문제를 해결해야 한다!

• 연산 횟수는 1초에 1억번 연산하는 것을 기준으로 생각한다.
  • 시간제한이 2초라면, 2억번 이하의 연선 횟수로 문제를 해결해야 한다!

 

시간 복잡도 활용

시간 복잡도를 계산하려먼 데이터의 개수와 제한 시간을 보면 된다.

🧐 [문제 1] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
- 시간 제한 : 2초
- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

• N(1 ≤ N ≤ 1,000,000)일 때, 1,000,000에 집중한다. 그리고 이에 알맞은 알고리즘을 선별해야 한다.

 

연산 횟수 계산 방법

시간 복잡도에 데이터의 크기를 대입하면 연산 횟수를 얻을 수 있다.

위 [문제 1]에서, 시간 제한이 2초이므로 연산 횟수가 2억번 이하여야 한다.

• 버블 정렬
  • 시간복잡도 : N^2
  • 연산 횟수 : (100만)^2
• 병합 정렬
  • 시간복잡도 : NlogN
  • 연산 횟수 : (100만)log(100만)

 

버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 부적합하다.

병합 정렬은 약 2천만 번(100만은 2의 약 20승)의 연산 횟수가 필요하므로 적합하다.

 

📌 데이터의 크기(N)을 단서로 이용하여 적합한 알고리즘을 추측할 수 있다!

 

 

시간 복잡도 도출 기준

내가 짠 코드의 시간 복잡도는 다음과 같은 기준으로 확인한다.

• 상수는 시간 복잡도 계산에서 제외한다.
  • 시간 복잡도가 3N이라고 하더라도, N앞의 상수 3은 시간복잡도 측면에서 영향력이 없으므로 무시해도 된다. 따라서 제외하고 N이라고 생각한다.
• 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
  • 2중 for문인 경우의 시간 복잡도는 N^2이 된다는 의미이다.

 

주의 사항

1. 알맞은 알고리즘을 선택하기
2. 비효율적인 로직을 찾아서 효율적으로 바꾸기