[TIL-12 / 230630] 알고리즘 - 시간복잡도

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

• 알고리즘에서 시간복잡도: 주어진 문제를 해결하기 위한 연산 횟수
• 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주
• 예제) 시간제한 2초 → 2억 연산 안에 답이 나와야 함.

1) 시간 복잡도 유형

1. 빅-오메가(Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법
2. 빅-세타(θ(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법
3. 빅-오(Ο(n)): 최악일 때(worse case)의 연산 횟수를 나타낸 표기법

public class timeComplexityExample1 {
    public static void main(String[] args) {
        // 1 ~ 100 사이의 값 랜덤 선택
        int findNumber = (int) (Math.random() * 100);
        for(int i=0;i<100;i++){
            if(i==findNumber){
                System.out.println(i);
                break;
            }
        }
    }
}

• 위 문제의 시간복잡도
  1. 빅-오메가(Ω(n)): 연산횟수 1번(최선)
  2. 빅-세타(θ(n)): 연산횟수 50번(100 / 2)(보통)
  3. 빅-오(Ο(n)): 연산횟수 100번(최악)
  → 데이터의 크기가 커지면 커질수록 차이가 많이 난다. 실제로 코딩테스트를 할 때는 최악의 경우(빅-오(Ο(n)))를 염두하고 시행한다.

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?

빅-오 표기법(O(n))의 시간 복잡도

 

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

[백준] 2750번 : 수 정렬하기 - JAVA [자바]

[백준] 2750번 : 수 정렬하기 - JAVA [자바]

백준(baekjoon) 2750 수 정렬하기

• 단순히 정렬하는 문제
• 시간 복잡도에서 중요한 것은 데이터의 갯수

예시)

1. 데이터의 개수가 1,000,000 → 1,000,000에 맞는 알고리즘을 써주는 것이 중요하다!
2. 제한시간 2초 → 2억 번 이하의 연산 횟수로 문제를 해결해야함.

• 연산 횟수 계산 방법
• 연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기
• 알고리즘 적합성 평가
  • 버블 정렬(N²) = (1,000,000)² = 1,000,000,000,000 > 200,000,000 → 부적합 알고리즘
  • 병합 정렬(NlogN) = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 적합 알고리즘
    • logN 계산 방법 → log2 = 1로 어림 계산 → log1024 = 10 … log1000000 = 약 20

1) 시간 복잡도 바탕으로 코드 로직 개선

시간 복잡도 도출 기준

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

예시

• 연산 횟수가 N인 경우

public class 시간복잡도_판별원리1 {
    public static void main(String[] args) {
        int N = 100000;
        int cnt = 0;
        for(int i = 0; i < N; i++){
            System.out.println("연산 횟수: " + cnt++);
        }
    }
}

• 연산 횟수가 3N인 경우

public class 시간복잡도_판별원리2 {
    public static void main(String[] args) {
        int N = 100000;
        int cnt = 0;
        for(int i = 0; i < N; i++){
            System.out.println("연산 횟수: " + cnt++);
        }
        for(int i = 0; i < N; i++){
            System.out.println("연산 횟수: " + cnt++);
        }
        for(int i = 0; i < N; i++){
            System.out.println("연산 횟수: " + cnt++);
        }
    }
}

→ 두 예제 코드의 연산 횟수는 3배 차이가 나지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다!

• 연산 횟수가 N²인 경우

public class 시간복잡도_판별원리3 {
    public static void main(String[] args) {
        int N = 100000;
        int cnt = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++) {
                System.out.println("연산 횟수: " + cnt++);
            }
        }
    }
}

→ 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출 → 이중 for 문이 전체 코드의 시간 복잡도 기준 → 시간 복잡도 N²

정리

실제 코딩 테스트에서 시간 초과가 발생했을 때

1. 문제가 되는 코드 부분을 도출
2. 더 효율적인 구조로 수정하는 작업으로 문제 해결

시간복잡도 따진다는 것은…

1. 알맞은 알고리즘 선택 기준
2. 비효율적인 로직 찾아서 효율적으로 바꾸는 것