Do it! 알고리즘 코딩테스트 자바 정리본 - 시간복잡도

minjung·2023년 1월 7일
0
post-thumbnail

💡시간복잡도

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.
일반적으로 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개

시간복잡도는 가장 많이 중첩되는 중첩문을 기준으로 봐야 한다.

0개의 댓글