💡시간복잡도
알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.
일반적으로 1초 = 1억 번의 연산을 의미한다.
문제에 시간제한이 2초로 되어있다면 2억 번의 연산 안에 답이 나와야 한다는 의미이다.
💡시간복잡도의 유형
시간복잡도의 유형에는 세 가지가 있다.
- 빅-오메가: 최선일 때
- 빅-세타: 보통일 때
- 빅-오: 최악일 때
예를 들어 100미만의 랜덤 숫자 num이 있고, 이 수를 구하기 위해 100번을 반복하는 for문을 작성한다고 가정하자.
그렇다면
빅-오메가는 num=0일 경우이므로 1
빅-세타는 평균치이므로 N/2
빅-오는 최악의 경우이므로 숫자 범위 내의 제일 마지막 숫자일 것이다. 따라서 N
우리는 코딩테스트를 진행할 때 최악의 경우, 빅-오를 기준으로 수행 시간을 계산하는 것이 좋다.
가장 최악의 케이스를 염두하고 코딩테스트에 임해야 한다.
💡시간복잡도 활용
시간복잡도를 따질 때는 데이터의 개수와 제한시간을 본다.
1번째 줄에 수의 개수 N(1 <= N <= 1,000,000) 일 때 1,000,000을 봐야한다. 그리고 이 수에 알맞은 알고리즘을 사용해야 한다.
연산 횟수 계산 방법
연산 횟수는 알고리즘 시간복잡도 x 데이터의 크기로 계산한다.
예를 들어, 버블정렬의 시간복잡도는 N^이다. 그리고 데이터의 개수가 100만이라고 가정한다면, 연산 횟수는 (100만)^이 된다.
만약 해당 문제의 제한시간이 2초라면 2억 번 내에 해결되어야 하는데, (100만)^의 값이 2억 번보다 크므로, 버블정렬은 시간초과로 인해 부적합한 알고리즘이 된다.
시간복잡도와 반복문
100번 반복하는 for문의 연산 횟수는 100이 된다. (N번)
이 for문이 3개 있다면 연산 횟수는 300이 된다. (3N번)
하지만 N앞의 상수는 사실 코딩테스트에서 크게 영향이 가지 않는다. 일반적으로 이 상수는 무시해도 된다. 두 코드의 시간복잡도는 같다고 봐도 된다.
하지만 100번 반복하는이중 for문일 경우는 연산 횟수가 10,000이 된다. (N의 제곱)
그래서 1차원 for문이 100개 있는 것보다 이중 for문 1개가 시간복잡도가 더 크다.
시간복잡도 비교
1차원 for문 100개 < 이중 for문 1개
시간복잡도는 가장 많이 중첩되는 중첩문을 기준으로 봐야 한다.
