Day-1 시간 복잡도

---

1. 시간 복잡도 표기

수행 시간은 1초에 1억 번의 연산을 하는 것으로 간주한다.

문제를 해결하기 위한 연산 횟수인 시간 복잡도는 3가지 유형으로 정의한다.

• 빅-오메가(Ω(n)) : best case
• 빅-세타(Θ(n)) : average case
• 빅-오(O(n)) : worst case

각각 최선, 보통, 최악일 때 연산 횟수를 나타낸다.

빅-오 표기법의 시간 복잡도

 

시간 복잡도는 n이 증가함에 따라 같이 증가한다. 증가 속도는 위 그림과 같다.

---

2. 시간 복잡도 활용하기

시간 복잡도로 코드의 로직을 개선할 수 있다.

시간 복잡도 계산에는 상수를 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

public class Main {
    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++);
        }
    }
}

 

하나의 for문은 연산 횟수가 N이다.

똑같은 for문이 세 개 있으므로 연산 횟수는 3N이다.

그러나 시간 복잡도 계산에서는 상수를 제외하므로 시간 복잡도는 O(n)이다.

 

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문이 두 번 중첩되어 연산 횟수가 N²이다.

따라서 시간 복잡도는 O(N²)이다.