1-1 시간복잡도 표기법 알아보기

알고리즘에서 시간복잡도란? "주어진 문제를 해결하기 위한 연산 횟수"

일반적으로 C++ 에서는 1억 번의 연산을 1초의 수행시간으로 예측한다고 한다.

시간 복잡도 정의하기

시간 복잡도를 실제로 정의하는 3가지 유형이 있다.

• 빅-오메가 : best case
• 빅-세타 : average case
• 빅-오 : worst case

예를 들어 0~99 사이의 무작위 값을 하나 맞추는 코드의 경우,

• 빅-오메가 표기법의 시간복잡도는 1번
• 빅-세타 표기법의 시간 복잡도는 N/2번
• 빅-오 표기법의 시간 복잡도는 N번이다!

그럼 코딩테스트에서는 어떤 시간복잡도 표기법을 사용해야 하나요?

코테에서는 (사실 당연하게도) 빅-오 표기법을 기준으로 수행시간을 결정하는 것이 좋다. 실제 테스트에서는 1개의 테스트 케이스로 성공/실패를 결정하지 않는다.
다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 성공(합격)으로 판단하기 때문에 시간복잡도를 판단할때는 최악의 케이스를 염두에 둬야 한다!

1-2 시간복잡도 활용하기

알고리즘 선택 기준으로 시간복잡도 활용하기

책에서는 정렬 학습을 완료했고, 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n^2), O(nlonn)이라고 알고 있다고 가정한다고 함!

연습문제 000

수 정렬하기 (백준 2750번, 시간 제한 2초)

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

시간 제한이 2초로 주어졌으므로 이 조건을 만족하려면 2억번 이하의 연산 횟수로 문제를 해결해야 한다고 생각하는거다!

• 연산 횟수는 1초에 1억번 연산하는 것을 기준으로 생각하기
• 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 하기

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간복잡도 n값에 데이터의 최대 크기를 대입하여 도출

위 공식에 대입해 각 알고리즘이 이 문제에 적합한지 아닌지 판단해볼 수 있다

알고리즘 적합성 평가

N개의 수가 주어지는데, N이 1 이상 100만 이하다. 따라서 시간복잡도 n 에 100만을 대입해서 계산해본다.

• 버블정렬 = (100만)^2 > 2억 -> 부적합!
• 병합정렬 = 100만 * log(100만) = 약 2천만 < 2억 -> 적합!!

정렬 알고리즘에 여러가지 종류가 있는데, 문제에서 주어지는 데이터의 범위와 시간복잡도를 알고 있으면 어떤 알고리즘은 선택해도 되는지 / 어떤 알고리즘은 선택하면 안되는지 알 수 있다.

그리고 이를 바탕으로 문제의 실마리를 찾을 수도 있다!

결론

데이터의 크기 N을 단서로 사용해야 하는 알고리즘을 추측해볼 수도 있다

시간복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 알고리즘 선택 이외에도, 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.

그리고 그러려면 가장 먼저 내 코드의 시간 복잡도를 도출할 줄 알아야 한다!

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

예시

코드 1 (연산 횟수 N)

int main(){
  int N = 1000;
  int cnt = 1;

  for (int i = 0; i < N; i++) {
    cout << "연산 횟수: " << cnt << endl;
  }
}

코드 2 (연산 횟수 3N)

int main(){
  int N = 1000;
  int cnt = 1;

  for (int i = 0; i < N; i++) {
    cout << "연산 횟수: " << cnt << endl;
  }
  for (int i = 0; i < N; i++) {
    cout << "연산 횟수: " << cnt << endl;
  }
  for (int i = 0; i < N; i++) {
    cout << "연산 횟수: " << cnt << endl;
  }
}

두 예제 코드의 연산 횟수는 3배 차이가 난다. 얼핏 봤을 때는 큰 차이가 나는 것 같지만, 빅-오 시간복잡도를 계산할때는 상수를 무시하기 때문에 두 코드 모두 시간복잡도는 O(n) 으로 동일하다.

코드 3 (연산 횟수 N^2)

int main(){
  int N = 1000;
  int cnt = 1;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << "연산 횟수: " << cnt << endl;
    }
  }
}

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 위 코드에서는 이중 for 문이 전체 코드의 시간복잡도 기준이 된다.

만약 일반 for문이 10개 더 있다고 해도 시간 복잡도는 변함 없이 N^2이다!