시간복잡도.. 뭔지는 아는데 코딩테스트에서 어떻게 쓰는데?
-
시간복잡도는 알고리즘을 선택하는 기준을 세울 수 있다!
ex) 데이터 셋 크기 n=1,000,000 일때 이를 오름차순으로 정렬해라(2초)
문제 시간 2초 => 1초에 1억번 정도의 연산이 가능함으로, 2억번이하의 연산을 통해 해결해야함
버블 정렬의 시간 복잡도 => n*n => 부적합
병합 정렬의 시간 복잡도 => nlogn => 적합 => 채택 -
만약 n=10,000이고 for문으로 만 번 연산하는 코드 vs 같은 경우 + for문 3개라고 하면
10,000(n) vs 30,000(3n) 이라고 생각할 수 있지만, 일반적으로 상수는 무시해 둘 다 n이다. -
시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출함 => n=10,000이고 1차원 for문 10개 + 이중 for문 1개라면 => 이중 for문 1개 기준으로 10,000 * 10,000이 시간 복잡도로 계산
정리
1. 알맞은 알고리즘 선택 기준
2. 비효율적인 내 로직 찾아서 효율적으로 바꿀때
.