최적의 시간 복잡도를 찾아서 🐠

* 이 글은 책 소프트웨어의 품격 3장을 참고하여 작성되었습니다. 잘못된 내용이 있다면 편하게 말씀해주세요 🙏🏻

 

'시간 복잡도'는 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미한다. 어떤 문제를 해결하는(같은 결과를 내는) 코드는 많다. 많은 코드 중 어떤 것이 좋을까? 보통 시간이 적게 걸리는 코드가 좋다고 한다. 바로 시간 복잡도가 낮은(효율이 좋은) 코드를 작성해야 한다. 

CS 이론이나 코딩테스트에서 시간 복잡도를 낮추기(효율을 좋게) 위해 여러 자료구조나 알고리즘을 최적화한다. 이때 예제는 하나의 함수에 대한 입, 출력을 최적화하여 빠른 코드를 작성한다.

하지만 실무에선 단순히 하나의 입,출력만 고려하는 것이 아니다. 다양한 메서드 간 연결과 함수의 사용 정도를 고려해 설계해야 한다. 예를 들어 A와 B 메서드가 연결되어있다고 하자. A 메서드의 복잡도를 낮출 수 있지만 그 결과로 B 메서드의 복잡도를 증가시킬 수 있다. 이런 트레이드오프(trade-off) 문제로 최적의 방법은 찾기 어렵고 완벽한 정답은 없다. 현재 상황에서 최적의 대안을 찾을 뿐이다.

 

아래 예제를 통해 많은 메서들 사이에 최적의 시간 복잡도를 찾아보자 🐠

---

예제

Statistic 클래스에 3가지 메서드를 구현해야 한다.

- public void insert(int n) : 정수 하나를 리스트에 추가한다.

- public double getAverage() : 리스트에 추가된 모든 정수의 산술 평균을 구한다.

- public double getMedian() : 리스트에 추가된 모든 정수의 중앙값을 구한다.

 

구현하는 방법은 많지만 두 가지 경우를 살펴보자.

 

Case1

멤버 변수에 총합 sum과 정수를 담을 리스트 numbers을 만든다.

- insert : 함수 실행마다 리스트에 데이터를 넣고 sum 멤버변수에 해당 값을 더한다 - O(1)

- getAverage : 함수 실행 시 멤버변수에서 총합 sum과 정수 개수(리스트의 크기)를 가지고 있기 때문에 한 번에 계산한다 - O(1)

- getMedian : 함수는 오름차순으로 정렬하여 중앙값을 계산한다. 이때 Collections.sort() 메서드는 Timsort로 복잡도 - O(n log n)

public class Statistic_case1 {

    private long sum;
    private List<Integer> numbers = new ArrayList<>();

    public void insert(int n) {
        numbers.add(n);
        sum += n;
    }

    public double getAverage() {
        return sum / numbers.size();
    }

    public double getMedian() {
        Collections.sort(numbers);
        int size = numbers.size();

        if (size % 2 == 1) {
            return numbers.get(size / 2);
        } else {
            return (numbers.get(size / 2 - 1) + numbers.get(size / 2)) / 2.0;
        }
    }

    public static void main(String ... args) {
        Statistic_case1 is = new Statistic_case1();
        is.insert(10);
        is.insert(5);
        is.insert(15);
        System.out.println("Average: " + is.getAverage() + "\t Median: " + is.getMedian());
        is.insert(15);
        System.out.println("Average: " + is.getAverage() + "\t Median: " + is.getMedian());
        is.insert(15);
        System.out.println("Average: " + is.getAverage() + "\t Median: " + is.getMedian());
    }
}

// 출력 결과
Average: 10.0	 Median: 10.0
Average: 11.0	 Median: 12.5
Average: 12.0	 Median: 15.0

 

Case2

- insert : case1과는 다르게 데이터를 정렬하며 추가한다. - O(n log n) 

- getAverage : case1과 동일하게 상수 시간으로 계산된다. - O(1)

- getMedian : case1과는 다르게 이미 데이터가 정렬되어 있기 때문에 상수시간으로 계산된다. - O(1)

public class Statistic_case2 {

    private long sum;
    private List<Integer> numbers = new ArrayList<>();

    public void insert(int n) {
        int i = 0;
        for (Integer k : numbers) { // 추가할 위치 검색
            if (k >= n) break;
            i++;
        }
        numbers.add(i, n); // 해당 위치 추가, 추가하며 데이터가 정렬된 순서로 쌓임
        sum += n;
    }

    public double getAverage() {
        return sum / numbers.size();
    }

    public double getMedian() {
        int size = numbers.size();

        if (size % 2 == 1) {
            return numbers.get(size / 2);
        } else {
            return (numbers.get(size / 2 - 1) + numbers.get(size / 2)) / 2.0;
        }
    }
}

 

	insert	getAverage	getMedian()
case1 (데이터 추가에 유리)	O(1)	O(1)	O(n log n)
case2 (결과 조회에 유리)	O(n log n)	O(1)	O(1)

case1은 빠르게 데이터 추가가 가능하다. 하지만 중앙값(getMedian) 결과를 조회하려면 느리다.

case2는 데이터 추가가 느리다. 하지만 평균과 중앙값 조회 모두 상수 시간으로 유리하다.

 

과연 case1과 case2의 중 무엇을 선택해야 할까?

미래에 사용자가 어떤 메서드를 더 많이 사용할지 고려해보면 된다. 만약 데이터 추가가 끊임없고 중앙값 조회가 적다면 case1을 선택하는 것이 옳다. 하지만 반대로 처음엔 데이터 추가가 많을지라도 10000개의 데이터만 들어가면 더 이상 추가할 일이 없다. 그 이후로 결과만 계속 조회해야 한다면 case2를 선택해야 한다.

 

이렇게 다양한 방법이 있고 메서드 간 서로 연결되어있다. 이때 단순히 하나의 메서드만 고려하는 것이 아닌 서로의 연결을 고려하고 미래의 사용량까지 생각해야 한다. 넓은 의미로 메서드간 연결은 클래스 간 연결로 바라볼 수 도 있다.

 

분할상환 시간 복잡도

 

분할상환 분석은 여러 번 실행하는 경우를 고려한다. 바로 미래의 효율성이 높은 알고리즘을 선택한다.

아래 예는 위에서 살펴본 case1과 case2가 있고, 새로운 case3가 있다고 가정하자. 이때 위와 같은 방식으로 고려한다면 어떤 방법을 선택해야 할까? 아까와 마찬가지로 경우에 따라 case1 또는 case2를 선택하는 것이 좋아 보인다. 왜냐면 case3는 모두 O(log n)이기 때문이다. 하지만 case3가 더 좋은 경우도 있다. 

	A 메서드	B 메서드	C 메서드
case1	O(1)	O(1)	O(n log n)
case2	O(n log n)	O(1)	O(1)
case3	O(log n)	O(log n)	O(log n)

 

---

결론

각 Case의 구현들은 특정 상황에서 다른 구현보다 좋지만 모든 경우에 최적의 경우는 없다. 

 

시간 복잡도를 고려하여 어떻게 좋은 코드를 작성할까?

- 여러 방식을 구현해보고 어떤 경우가 최적의 문제인지 선택하자.

- 먼 미래의 메서드 사용량을 추측하여 고려하자(앞으로의 시나리오 고민, 분할상환 시간 복잡도 등)

 

 

 

⛓ Reference

책, 소스코드 (Java)

http://www.yes24.com/Product/Goods/103599789

https://github.com/AcornPublishing/seriously-software

 

분할상환분석 - 위키

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0%EC%83%81%ED%99%98%EB%B6%84%EC%84%9D

 

소프트웨어의 품격 스터디

https://github.com/Quokka-Squad/Seriously-Good-Software