시간 복잡도

[지금 무료]Do it! 알고리즘 코딩테스트 with JAVA| 하루코딩 - 인프런 강의

위의 강의를 참고하여 정리하였습니다. 

 

시간 복잡도란?

주어진 문제를 해결하기 위한 연산의 횟수를 의미합니다. 

 

💡 수행시간

1억번의 연산을 1초의 시간으로 간주합니다. 

➡️ 즉, 2초의 제한시간이 주어진다면 2억번의 연산안에 문제를 해결해야 합니다. 

 

---

 

시간 복잡도 유형

최선	보통	최악
빅 오메가 ( Ω (n) )	빅 세타 ( θ(n) )	빅 오 ( O(n))

 

public class Main {
    public static void main(String[] args) {
        // 0 ~ 99사이의 랜덤 값
        int n = (int) (Math.random() * 100);

        for (int i = 0; i < 100; i++) {
            if (i == n) {
                System.out.print(i);
                break;
            }
        }
    }
}

 

 

n = 0인 경우

for문은 오직 1번만 실행되는 빅 오메가의 시간 복잡도를 가지게 됩니다.  

 

n = 32, 54, 68 . . . . 인 경우

for문은 N(100번)을 기준으로 평균 N/2번 실행하게 되는 빅 세타의 시간 복잡도를 가지게 됩니다. 

 

n = 99인 경우

for문을 모두 실행하고 나서 문제가 해결되는 빅오 시간 복잡도를 가지게 됩니다.

 

 

코딩 테스트에서 고려해야하는 시간 복잡도는?

코딩 테스트에서는 입력 데이터의 크기(N)이 다양하게 주어집니다.

따라서, 최선·평균에 맞춘 분석보다는 최악의 경우를 기준으로 한 빅-오를 사용하는 것이 좋습니다.

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기 

 

[예시]

시간 복잡도: O(N^2) , 데이터 크기: 1000

 

➡️ 1000^2인 1,000,000의 연산 횟수가 나옵니다.

---

 

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

1. 상수는 시간 복잡도 계산에서 제외

 

O(N) 예시

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        for (int i = 0; i < n; i++) {
            System.out.println(i + "번째 수행");
        }
    }
}

 

for문이 3개 존재하면 시간 복잡도는 O(3N)이지만, 실제 실행 시간은 O(N)과 큰 차이가 없습니다.
따라서 시간 복잡도를 계산할 때는 상수를 제외하고 표기합니다.

 

 

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준

 

O(N^2)

public class Main {
    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문은 O(N^2)의 시간 복잡도를 가지기 때문에 단일 for문이 여러 개 있더라도 시간 복잡도는 변하지 않고 O(N^2) 로 유지됩니다.

 

만약 3개의 중첩된 for문이 있다면?

이중 for문 수백개보다 3중 for문의 시간 복잡도가 더 크기 때문에 전체 시간 복잡도는 3중 for문의 시간 복잡도를 기준으로 계산됩니다. 

 

따라서, 시간 복잡도는 중첩된 for문을 기준으로 계산해야 합니다.