시간복잡도 분석

시간복잡도란걸 몰라도 프로그램을 짜는데 문제가없다

하지만 알아야 조금이라도 더 좋은 프로그래밍을 할수있다. 쌓이다보면 엄청나게 크다고 생각한다.

 

시간 복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로 알고리즘이

실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에대한 함수로 표현한 것입니다.

기본적인 연산이란 더작게 쪼갤수없는 최소크기의 연산이라고 볼수있습니다.

 

프로그래밍에서는 전체언어에 해당하는

• 사칙연산
• 실수형 변수의 대소 비교
• 한 변수에 다른 변수 대입하기

등이있습니다.

 

반면 다음과같은 연산은 반복문을 포함하기때문에 기본적인 최소크기의 연산이 아닙니다.

 

• 정렬
• 두 문자열 비교

 

알고리즘의 성능을 측정할때 어떻케 해야할까요

속도로는 측정할수없다.

언어마다 전부 다르며 구동하는 환경마다 다르다.

그럼 이런 알고리즘의 시간을 무엇을 어떻케 기준으로 잡아서 측정해야할까요

 

대부분의 알고리즘은 입력의 크기에 대응하는 반복문을 갖고있습니다.

그리고 이러한 입력의 크기가 커질수록 알고리즘의 수행시간은 반복문에게 의존하게됩니다.

 

따라서 널리쓰이는 시간복잡도분석시에 알고리즘의 수행 시간을 반복문이 반복돼는 횟수로 측정합니다.

이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현합니다.

    public int majority1(List<Integer> a){

        int n = a.size();
        int majority = -1, majorityCount = 0;

        for(int i = 0; i < n; i++){

            int v = a.get(i), count = 0;

            for(int j = 0; j < n; ++j){
                if(a.get(j) == v){
                    ++count;
                }
            }

            if(count > majorityCount){
                majorityCount = count;
                majority = v;
            }

        }

        return majority;

    }

주어진 배열에서 가장많이 등장하는 숫자를 반환하는 자바 메소드입니다.

 

입력으로 주어지는 숫자들이 100점만점인 중간고사 점수입니다.

이 처럼 숫자의 범위가 작다면 배열을 이용해 각 숫자가 등장하는 횟수를 쉽게 셀 수 있습니다.

 

이코드에는 두개의 반복문이있습니다.

하나는 n번 수행되고, 다른하나는 100번 수행되므로 전체 반복문의 수행횟수는 N + 100 이 됩니다.

 

근데 n의 크기가 커지면 커질수록 두번째 반복문의 비중이 줄어들게됩니다.

따라서 궁극적으로 이알고리즘의 수행시간은 N 이라고 씁니다.

 

그리고 또 하나의 코드를 살펴봅시다.

 

    public int firstIndex(int a[], int searchValue){

        for (int i = 0; i < a.length; i++) {
            if(a[i] == searchValue)
                return i;
        }
        return -1;
        
    }

위 코드는 배열에서 주어진 숫자의 위치를 반환하는 함수입니다.

 

이럴경우 반복문의 횟수는

찾는 원소의 위치에 따라 달라집니다.

운 좋을 경우 = 1

운 나쁠 경우 = a.length

 

이와 같이 입력의 종류에 따라 수행시간이 달라지는 경우를 고려하기위해서

우리는 최선/ 최악의 경우 그리고 평균적인 경우에대한 수행시간을 각각 따로 계산합니다.

 

다음과같이 계산 할 수 있습니다.

 

• 최선의 수행 시간 : 찾으려는 원소가 배열의 맨 앞에 있을때 알고리즘은 한번 실행합니다.
• 최악의 수행 시간 : 배열에 해당 원소가 없을때 알고리즘은 a.length 번 반복합니다.
• 평균의 수행 시간 : 배열에 원소의 등장 확률이 모두 같다고 생각하며 알고리즘은 N/2 번 반복 됩니다.

 

이 세개의 기준 중 널리 대부분의 경우 사용하는것은

최악의 수행 시간 혹은 수행 시간의 기대치 (평균의 수행 시간) 입니다.

이 두 기준은 따로 구분되지않고 쓰이는데, 여러 알고리즘에서 이 두 기준이 거의 똑같습니다.