저장용

시간복잡도?

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

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

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

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)라고 한다.