시간복잡도(Java)

✔ 알고리즘 선택의 기준이 되는 시간 복잡도 

 

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 

 

✔ 시간 복잡도 유형 

• 빅 - 오메가 : 최선일 때
• 빅 - 세타 : 보통일 때
• 빅 - 오 : 최악일 때

--> 코딩테스트를 풀 때는 최악인 경우까지 생각해야 한다. 즉, 빅 - 오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.

 

✔ 시간 제한이 2초라는 조건을 만족하려면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다. 

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

 

이 문제의 경우 

- 버블 정렬 : 10억번 이상의 연산 횟수로 부적합 알고리즘 

- 병합 정렬 : 약, 2000만번의 연산 횟수로 적합 알고리즘 

 

✔ 시간 복잡도 도출 기준 

1. 상수는 시간 복잡도 계산에서 제외한다. 

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. 

 

✔ 시간 복잡도란

1. 알맞은 알고리즘을 선택 할 때

2. 비효율적인 로직을 찾아 효율적으로 바꿀 때 

의 기준이 된다.