[개인 공부] 점금적 시간 표기법(O표기), 주먹구구 법칙

안녕하세요, HoonIOS입니다.

저번에는 기초 알고리즘과 시간 복잡도(추가사항)에 대해 알아봤는데요

(이곳을 클릭하시면 저번 포스팅 내용을 보실 수 있습니다.)

 

이번 시간에는 O표기법, 주먹구구 법칙에 대해서 알아보겠습니다.

 

점근적 시간 표기: O 표기

- 우선 O표기법의 정의 대해 알아보겠습니다. O표기법이란 주어진 함수에서 가장 빨리 증가하는 항만 남긴 채 나머지 값들은 다 버리는 표기법입니다. 즉 쉽게 말해 제일 높은 다항 차만 빼고 나머지 값을 버린다고 생각하시면 되겠습니다.

- 알고리즘에서는 입력의 크기가 두개 이상의 변수로 표현될 때는 그중 가장 빨리 증가하는 항들만을 떼놓고 나머지를 버린다는 의미입니다.

- 예를 들어 N² + N의 알고리즘 입력 크기가 나왔다면 여기서 O표기법으로는 N² 이 되는 것을 말합니다.

- O표기법에는 특이한 경우도 있다. 예를 들어 확인해 보겠습니다.

N²M + NlgM + NM² 의 입력의 크기 값이 있다고 가정해 보겠습니다. 이것을 O표기법으로 바꾸면 O(N²M  + NM²)가 됩니다.

이렇게 표기되는 이유는 한쪽이 빠르게 증가한다고 할 수 없기 때문에 둘 다 표기에 포함을 시킨 것입니다.

- 또 위 알고리즘은 1만큼의 시간밖에 걸리지 않는다고 쓰기 때문에 우리는 이런 알고리즘을 상수 시간 알고리즘이라고 부릅니다.
- 상수 시간 알고리즘의 표기로는 O(N), O(1)이라고 표기할 수 있고 가장 효율적인 알고리즘입니다.

- O표기법의 다른 예를 한번 들어보겠습니다. 

삽입 정렬로 예를 들어 최선일 때 while문이 입력 개수에서 한 번만 돌고 종료하는 경우의 경우 시간 복잡도는 O(1)로 보아야 하기 때문에 for문에 자우되 N이 되고 최악의 경우는 while문이 입력 개수만큼 N이 도는 경우의 경우 시간 복잡도가 O(N)이 되고 for문에 N을 받으면 시간 복잡도는 O(N²)이 되는 것을 알 수 있습니다.

 

이제 O표기법도 알아보았겠다, 수행 시간 어림짐작을 해보는 법을 알아보겠습니다.

수행 시간을 어림짐작하기 위한 가장 큰 방법은 주먹구구 법칙이 있습니다.

 

주먹구구 법칙

- 우선 어떤 알고리즘이 이 문제를 시간 안에 해결할 수 있는지를 알기 위해서는 프로그램을 작성하기 전에 입력의 최대  크기와 알고리즘의 시간 복잡도를 보고 어림짐작할 수 있어야 합니다.

- 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적이라도 짐작하는 것이 가능하지만 수행 시간을 짐작하는 것은 다음의 환경 때문에 어려운 부분이 있습니다.

1. cpu의 클록 속도
2. 메모리의 접근 패턴
3. 운영체체와 컴파일러의 버전

- 그렇지만 이런 요소들은 프로그램의 수행 속도에 끼치는 영향은 기껏해야 몇 배정도 차이가 나지만 알고리즘의 시간 복잡도에 따라 프로그램은 수천 배, 수만 배정도 차이가 날 수 있습니다.

 

- 그럼 이제 알고리즘 시간 복잡도를 짐작할 수 있는 주먹구구 법칙에 대해 알아보겠습니다.

• 주먹구구 법칙이란?
  - 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10⁸)을 넘어가면 시간제한을 초과할 가능성이 있다는 법칙입니다.
  - 그렇지만 시간 복잡도와 입력 크기 외의 요소들(위에서 말씀드린 환경들 기억나시죠?)이 프로그램의 수행 속도로를 열 배 정도는 쉽게 바꿔놓을 수 있어서 무조건 1억이 초과하지 않는다고 시간 안에 실행될 거라고 확신을 가지지 않는 것이 충분히 여유(예측 수행 횟수가 기준의 10% 이하인 경우와 기준의 10배를 넘는 경우에만 이 법칙을 적용한다.)를 두는 것이 좋습니다.

- 주먹구구의 의미에 대해 알아보았는데요, 예측일 뿐이니 절대로 확신하지 않으시는 게 좋습니다. 왜냐하면 기준보다 느리지만 시간 안에 수행되는 알고리즘도 얼마나 있고 가끔은 이 기준보다 빠르지만 시간 안에 수행되지 않는 프로그램도 있기 때문이다.

 

- 시간 복잡도 외에 고려해야 하는 요소를 알아보겠습니다.

1. 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: O표기법은 최 고차항을 제외하고 나머지를 제거하는데 따라서 입력의 최대 크기를 대입한 결과는 어디까지 예측값일 뿐이라는 것입니다!
2. 반복문의 내부가 복잡한 경우: 반복문 내부는 단순할수록 좋은데, 반복문의 내부가 길거나 시간이 많이 걸리는 연산(실수 연산 등)을 많이 사용할 경우 가정보다 오래 걸릴 수밖에 없다. 그러나 이 반대로 반복문의 내부가 아주 단순한 경우는 이 가정보다 프로그램이 빨리 수행된다.!
3. 메모리 사용 패턴이 복잡한 경우: 현대의 CPU는 메모리에 있는 자료를 직접 접근하는 대신 캐시를 이용하는데 캐시는 인접한 자료들도 함께 가져오기 때문에 사용하는 프로그램은 매번 자료를 가져올 필요 없이 캐시에 저장된 자료를 사용하면 되는데, 이런 차이는 시간 복잡도보다는 프로그램 수행 속도에 영향을 끼친다.
4. 언어와 컴파일러 차이: 이거는 제일 처음 말씀드렸던 시간 복잡도 분석에 포스팅했는데요, 같은 방식으로 알고리즘을 풀어도 언어마다 시간 차이가 많이 나는 것을 알 수 있습니다.
5. 구형 컴퓨터인 경우: 이거는 당연한 거겠죠? ㅎㅎㅎ

- 이제는 배열에서 최대 합을 갖는 부분 구간을 찾는 문제를 푸는 알고리즘을 통해 O(N³), O(N²), O(nlgn), O(N)의 시간 복잡도로 푸는 알고리즘을 알아보겠습니다.

 

- O(N³) 시간 복잡도인 알고리즘으로 배열의 모든 구간을 순회해서 기합을 계산하는 알고리즘입니다.

Const int Min = numberic_limits<int>::min();

int inefficientMaxSum(const vector<int>& A) {
	int N = A.size(), ret = Min;
    for(int i = 0; i < N; ++i) { //입력 N
    	for(int j = i; j < N; ++j) { //입력 N
        //A[i...j]구간의 합을 구하는 부분
        int sum = 0;
        for(int k = i; k <= j; k++) { //입력 N
        	sum += A[k];
            ret = max(ret,sum); //최솟값을 지정해준 값과 합과 비교
        }
    return ret;
 }

-이 알고리즘은 for문이 총 3번이고 입력값이 총 N이 3번 있으므로 시간 복잡도는 O(N³)이 됩니다.

-이번에는 시간 복잡도가 O(N²)인 경우 for문이 총 2번인 경우에 대해 알아보겠습니다.

int betterMaxSum(const vector<int>& A) {
	int N = A.size(), ret = MIN;
    for(int i = 0; i < N; ++i) {
    	int sum = 0;
        for(int j = i; j < N; ++j) {
        	//i...j합을 구한다.
            sum += A[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}

 

- 이번 방법은 분할 정복 기법을 이용하겠습니다.

 

- 분할 정복 기법이란 입력받은 배열을 절반으로 잘라 왼쪽 배열과 오른쪽 배열로 나누고 이때 각 경우의 답을 재귀 호출과 탐욕 법을 이용해서 계산하는 것을 분할 정복 알고리즘이라고 합니다.

- 여기서 재귀란? 자기 자신을 호출하는 형식입니다.

- 탐욕법이란? 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 기법이라고 할 수 있습니다. 따라서 결괏값은 최적의 해를 보장해주지는 않는다는 단점이 있습니다.

- 이 코드는 재귀 함수를 사용하고 for문이 n만큼 발생하므로 O(nlgn)이 된다.

int fastMaxSum(const vector<int>& A, int lo, int hi) {
//값이 하나만 있을 경우
	if(lo == hi) return A[lo]
    //분할 기법을 위해 반으로 나눈다.
    int mid = (lo + hi) / 2;
    
    //A[i...mid]구간의 최대값을 구한다.
    int left = MIN, right = MIN, sum = 0;
    for(int i = mid; i >= lo; --i) {
    	sum += A[i];
        left = max(left, sum);
    }
    //A[mid+1...i]구간의 최대값을 구한다.
    sum = 0;
    for(int j = mid; j >= lo, ++j) {
    	sum += A[j];
        right = max(right, sum);
    }
    
    //최대 구간이 두 조각중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
    int single = max(fastMaxSum(A,lo,mid), fastMaxSum(A,mid+1,hi));
    
    return max(left + right, single) //각구간의 최대값을 더한 값과 single값을 비교한다.

- 이번에는 선형 시간(N)에 푸는 방법으로 동적 계획법을 사용하겠습니다.

- 동적 계획법이란?

전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식

 

- A[i]을 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수 maxAt(i)를 정의해보면 A[i]에서 끝나는 최대 합 부분 구간은 항상 A[i]하나만 구성되어 있고 A[i-1]을 오른쪽 끝으로 갖는 최대 부분 구간의 오른쪽 A[i]를 붙인 형태로 구성되어 있음을 증명할 수 있다.

- 식으로 설명을 하면

maxAt(i) = max(0,maxAt(i-1)) + A[i]

 

- 이것의 반복적 동적 계획법을 이용한 풀이는 다음과 같다. 반복문이 한 번이므로 시간 복잡도는 O(N)입니다.

//A[]의 연속된 부분 구간의 최대 합을 구한다.
int fastestMaxSum(const vector<int>& A) {
	int N = A.size(), ret = MIN, psum = 0;
    for(int i = 0; i < N; ++i) {
    	psum = max(psum,0) + A[i];
        ret = max(psum, ret);
    }
    return ret;
}

- 한 문제를 여러 개의 알고리즘으로 해결한 위 예시를 보았는데요, 각 시간 복잡도는 1초 내에 수행할 수 있는 수행 횟수가 알고리즘 간에 100개까지 차이 나는 것을 볼 수 있다.

- 따라서 위 결과에 따라서 단순한 반복문 내부, 시간 복잡도 분석 과정에서 생략된 결과가 이런 결과를 나타내는 겁니다.

 

 

이번 시간에는 O표기법, 주먹구구 법칙, 시간 복잡도 예시까지 알아봤는데요

 

다음 시간에는 P, NP, NP-완비에 대해 알아보겠습니다.

 

오늘 하루도 행복한 하루 되시고 긴 글 읽어주셔서 감사합니다. :)