저장용

시간복잡도?

모든 알고리즘은 수행하는데 필요한 시간이 있다. 시간복잡도는 다음과 같이 정의할 수 있다.

알고리즘을 수행하는데 필요한 총 시간

알고리즘의 수행시간에 영향을 끼치는 요인들은 다음과 같다.

1. 실행되는 프로세서가 단일프로세서인지 멀티프로세서인지
2. 운영체제가 32비트인지 64비트인지
3. 컴퓨터의 읽고 쓰는 속도
4. 산술연산, 논리연산, 반환 값과 할당 작업 등
5. 입력데이터

알고리즘의 시간복잡도를 계산할 때, 입력데이터를 제외한 나머지 것들은 고려하지 않는다(하드웨어에 달린 문제이기에). 프로그램이 입력데이터에 따라 어떻게 수행되는 지에 초점을 맞춘다.

컴퓨터 시스템마다 전부 다르기 때문에 시스템 설정(1,2,3,4)에 기반한 알고리즘 시간복잡도 계산은 매우 복잡하다. 그렇기 때문에 여기서는 특정한 시스템 모델로 가정하고 계산하자(점근적 표기법은 다음에 알아보자).

시간 복잡도 계산을 위한 모델을 다음과 같이 정의해보자

1. 싱글 프로세서
2. 32비트 운영체제
3. 순차적 실행
4. 산술 연산과 논리 연산에 1 단위 시간 필요
5. 할당과 반환값에 1 단위 시간 필요
6. 읽고 쓰는 연산에 각각 1 단위 시간 필요

이제 이 모델로 시간 복잡도를 계산해보자

예시 1

int sum(int a, int b){
    return a + b;
}

위의 코드에서 a+b를 수행하는데 1 단위 시간이 필요하고, 값을 반환하는데 1 단위 시간이 필요하다. 이 코드를 수행하는데 총 2 단위 시간이 필요하며, 이 값은 입력 값 a, b에 상관없이 일정하다.

입력 값에 상관 없이 수행하는데 필요한 시간이 변하지 않을 때, 이 시간 복잡도를 상수 시간 복잡도(Constant Time Complexity) 라고 한다.

예시 2

int sum(int A[], int n){
    int sum = 0, i;         // 1
    for(i = 0; i < n; i++)	// 1 + (n+1) + n
    	sum = sum + A[i];   // 2n
    return sum;             // 1
}                           // total : 4n + 4

sum에 0을 저장하는데 1 단위 시간

i = 0 을 저장하는데 1 단위 시간

i < n 을 비교(논리 연산) 1 단위 시간이 n+1번

i++을 수행하는데 1 단위 시간이 n번

sum = sum + A[i]를 수행하는데 2 단위 시간이 n번

sum을 반환하는데 1 단위 시간

총 4n+4시간이 걸린다. 이는 고정된 값이 아니며 입력 값인 n에 의해 바뀐다.

입력 값이 증가함에 따라 시간의 양이 선형적으로 증가할 때, 이 시간 복잡도를 선형 시간 복잡도(Linear Time Complexity)라고 한다.

어느 알고리즘 이든 다음과 같은 이유들로 컴퓨터의 메모리를 필요로 한다.

1. 프로그램 명령어 저장
2. 상수 저장
3. 변수 저장
4. 기타 등등

알고리즘의 공간복잡도는 다음과 같이 정의할 수 있다.

알고리즘이 수행되는데 필요한 메모리의 총량

프로그램이 실행될 때 보통 세가지 이유로 컴퓨터 메모리를 사용한다.

1. Instruction Space: 컴파일된 명령어들을 저장하는 메모리의 양
2. Environmental Stack: 함수 호출시 부분적으로 실행 된 함수의 정보를 저장하는 데 사용되는 메모리의 양
3. Data Space: 모든 변수와 상수를 저장하는 메모리의 양

알고리즘의 공간복잡도를 분석할 때, 보통 Instruction Space와 Environmental Stack은 무시하고 Data Space만을 고려한다. 변수, 상수, 구조체 등이 저장되는데 필요한 메모리만을 계산하겠다는 뜻이다.

예시 1

int square(int a) {
    return a*a;
}

위 코드에서는 변수 'a'를 저장하는데 2바이트, return value를 위해 2바이트가 사용된다. input값 'a'에 대해 4바이트가 고정적으로 필요하다.

알고리즘이 어느 input value에 대해 항상 고정된 공간을 필요로 할 때, 이를 상수 공간 복잡도(Constant Space Complexity)라 한다.

예시 2

int sum(int A[], int n){
	int sum = 0, i;
	for(i = 0; i < n; i++)
		sum = sum + A[i];
	return sum;
}

A[]를 저장하기 위해 'n*2' 바이트, n을 저장하기 위해 2바이트, 지역변수 sum, i를 위해 각각 2바이트씩, return value를 위해 2바이트가 필요하다. 즉, 이 코드를 수행하기 위해 '2n + 8' 바이트가 필요하며 인풋인 n에 메모리 양이 의존하게 된다.

알고리즘이 어느 input value가 증가함에 따라 필요한 공간이 선형적으로 증가하는 것을 선형 공간 복잡도(Linear Space Complexity)라고 한다.