Ch.07 일상적인 코드 속 빅 오 (도서 요약 "누구나 자료구조와 알고리즘")

코드가 얼마나 빠른지 파악하는 것이 최적화의 첫 번째 단계이다. 더욱이 코드가 빅 오 표기법 관점에서 어떤 카테고리에 해당하는지 알면 최적화의 필요성을 판단할 수 있다.

 

7. 1  짝수의 평균

---

만약 수 배열을 받아 모든 짝수의 평균을 반환하는 메서드가 있다고 하자.

 

public double averageOfEvenNumbers(int[] arr) {
    int sum = 0;
    int count = 0;

    for(int i=0; i<arr.length; i++) {
        if(arr[i] % 2 == 0) {
            sum += arr[i];
            count++;
        }
    }

    return (double)sum / count;
}

 

알고리즘의 효율성을 알아보기 위해선 값 N개를 처리하는 데 얼마나 많은 단계 수가 필요한지 알아야 한다.

 

핵심은 배열 내 각 수를 순회하는 '루프'이므로, 루프를 먼저 분석하자. 위 루프는 원소 N개를 순회하니 알고리즘에는 최소 N단계가 필요하다.

 

하지만 들여다보면 '짝수'인 경우 sum을 수정하고 count++를 하는 두 단계를 더 거친다. 따라서 홀수일 때보다 짝수일 때 세 단계를 더 실행한다. 모든 수가 짝수인 최악의 시나리오라면, 매 루프마다 세 단계를 수행해야 한다. 즉 데이터 원소가 N개일 때 알고리즘은 3N 단계가 걸린다.

 

이 밖에 루프 밖에서 sum, count 변수를 선언 및 초기화하는 두 단계와 평균을 구하는 단계까지 더 걸리므로 총 단계 수는 3N + 3이다. (하지만 빅 오 표기법은 상수를 무시하니 단순히 O(N)이라고 부른다)

7. 2  단어 생성기

---

문자 배열로부터 두 글자짜리 모든 문자열 조합을 만드는 알고리즘을 만들어보자.

 

public ArrayList wordBulider(String[] arr) {
    ArrayList<String> list = new ArrayList<>();

    for(int i=0; i<arr.length; i++) {
        for(int j=0; j<arr.length; j++) {
            if(i != j) {
                list.add(arr[i] + arr[j]);
            }
        }
    }

    return list;
}

​

알고리즘에서 바깥 루프는 N개 원소를 모두 순회하고 각 원소마다 안쪽 루프는 다시 N개 원소를 모두 순회하니 대표적인 O(N²) 알고리즘이다.

7. 3  배열 예제

---

이번 예제에서는 배열에서 소규모 샘플을 취하는 메서드를 생성한다. 배열의 맨 앞과 가운데, 맨 뒤 값을 가져와보자.

 

public ArrayList sample(int[] arr) {
    ArrayList<Integer> list = new ArrayList<>();

    list.add(arr[0]);
    list.add(arr[arr.length / 2]);
    list.add(arr[arr.length - 1]);

    return list;
}

 

해당 메서드는 N이 얼마든 단계 수가 동일하다. 배열의 시작과 중간, 마지막 인덱스 읽기는 배열 크기에 상관없이 딱 한 단계다. 단계 수가 상수이므로, 즉 N에 관계없이 일정하므로 이 알고리즘은 O(1)이다.

7. 4  의류 상표

---

새로 생산한 의류 품목 배열을 받아 상표에 넣어야 할 텍스트를 생성하는 메서드를 만들어보자.

상표에는 품명과 1부터 5까지의 사이즈가 들어가야 한다. 

 

public ArrayList markInventory(String[] arr) {
    ArrayList<String> list = new ArrayList<>();

    for(int i=0; i<arr.length; i++) {
        for(int j=1; j<6; j++) {
            list.add(arr[i] + "Size: " + j);
        }
    }

    return list;
}

 

중첩 루프가 들어간 코드라서 O(N²)으로 생각할 수 있지만 아니다.

바깥 루프가 N번 실행되는 동안 안쪽 루프는 '5번'으로 고정되어 실행된다. 따라서 안쪽 루프는 N이 얼마든 항상 5번만 실행되기 때문에 알고리즘은 총 5N번 실행되고 빅 오는 상수를 무시해 결국 O(N)이다.

7. 5  팰린드롬 검사기

---

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절이다.

어떤 문자열이 팰린드롬인지 판단하는 메서드는 다음과 같다.

 

public boolean isPalindrome(String arr) {
		
    int leftIndex = 0;
    int rightIndex = arr.length() - 1;

    while(leftIndex < arr.length() / 2) {
        if(arr.charAt(leftIndex) != arr.charAt(rightIndex)) {
            return false;
        }

        leftIndex++;
        rightIndex--;
    }
    return true;
}

 

N은 메서드에 전달된 String의 크기다. while 루프 안이 알고리즘의 핵심이다. 문자열 중간에 도달할 때까지만 실행되는 루프라서 N / 2 단계를 실행한다는 뜻이다. 하지막 빅 오는 상수를 무시한다. 따라서 해당 알고리즘은 O(N)이다. 

7. 6  모든 곱 구하기

---

수 배열을 받아서 모든 두 숫자 조합의 곱을 반환하는 알고리즘은 다음과 같다.

 

public ArrayList twoNumberProducts(int[] arr) {
    ArrayList<Integer> list = new ArrayList<>();

    for(int i=0; i<arr.length; i++) {
        for(int j=i+1; j<arr.length; j++) {
            list.add(arr[i] * arr[j]);
        }
    }
    return list;
}

 

바깥 루프는 N번 실행한다. 안쪽 루프의 j는 항상 오른쪽 인덱스에서 시작하므로 안쪽 루프의 단계 수는 바깥 루프를 한 번씩 돌 때마다 1씩 줄어든다. 안쪽 루프는 N² / 2 단계를 실행하지만, 빅 오는 상수를 무시해 O(N²)으로 표시한다.

7. 7  마무리

---

지금까지 많은 종류의 알고리즘을 분석해 시간 복잡도를 분류했다.

다음 장부턴 알고리즘의 속도를 올리는 가장 유용하고 일반적인 도구를 배울 것이다. 

---

'누구나 자료구조와 알고리즘' / 저자: 제이 웬그로우

해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.

오로지 학습용으로 작성하였음을 밝힙니다.

더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.