더북(TheBook)

2.2.3 여러 알고리즘을 사용할 때 시간 복잡도 생각해보기

하나의 풀이에 여러 개의 알고리즘을 사용한다면 시간 복잡도는 어떻게 계산될까요? 예를 들어 다음 코드처럼 길이가 N인 배열을 이중 반복문으로 순회하는 것은 O(N2)의 시간 복잡도로 나타낼 수 있습니다.

int[] arr = ... // 길이가 N인 배열

for (int a : arr) {
    for (int b : arr) {
        System.out.println(a + " + " + b + " = " + (a + b));
    }
}

순회와 별개로 다음과 같이 배열을 다시 한 번 순회한다면 추가적으로 O(N)의 시간 복잡도가 발생합니다. 이때 총 시간 복잡도는 O(N2+N)이 될 것입니다.

int[] arr = ... // 길이가 N인 배열

for (int v : arr) {
    System.out.println(v);
}

for (int a : arr) {
    for (int b : arr) {
        System.out.println(a + " + " + b + " = " + (a + b));
    }
}
신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.