[Algorithm] 코드 블럭 단위 복잡도 분석

개요

---

코드 블럭은 C++일수도 있고, 수도코드, 의사코드 일수도 있다. 점근적으로 n이 커질 때, 점근적 런타임과 점근적 메모리 문제의 크기를 설명하는 변수, n이던 아니던 vertex의 개수던 edge의 개수던 이런 parameter를 표현하는 것이 첫번째 단계이다.

 

알고리즘의 asymptotic behavior은 이 알고리즘이 n이 커졌을 때, 문제의 크기가 커졌을 때 어떻게 행동하는지, 과연 이 알고리즘이 n이 아주 큰 상황에서도 잘 동작하는지에 대한 정보를 제공한다.

 

예를 들어 A는 세타오브 n square이고 B는 n log n일 때 n의 값이 2k일 때는 A의 경우 4k square B의 경우 2k log k + 2k 이다. 하지만 2k에서 10k로 5배 증가시킨다면 A의 요구시간은 5 * 5 = 25배 증가하게 되고 B의 요구시간은 5배 증가하게 된다. 때문에 A는 n이 커지면 더 많은 계산량이 필요하기 때문에 복잡도를 낮추려는 노력이 필요하다.

---

복잡도를 분석하기 전에 알아야 할 내용

---

=

+ - * / % ++ --

&& || !

& | ^ ~

== != < <= => >

new delete

위의 연산들은 constant time에 수행될 수 있다.

즉 정해진 fixed number of cycle에 수행될 수 있다.

왜냐하면 machine instruction에 mapping되기 때문에 모두 linear 즉 선형적인 시간에 수행될 수 있다.

---

C++코드 시간복잡도 분석

---

 

int *Increase_Capacity(int *_array, int_n, int _delta)
{
	int *array_old = _array;
    _array = new int [ _n + _delta ];
    
    for(int i = 0; i < _n; i++)
    {
    	_array[i] = array_old[i];
    }
    
    delete [] array_old;
    return _array;
}

위 함수의 code review와 시간복잡도를 분석해 볼 것이다.

int *Increase_Capacity(int *_array, int_n, int _delta)
{
	int *array_old = _array;
    _array = new int [ _n + _delta ];

첫 번째 코드 블럭이다.

array_old라는 포인터 변수를 선언하고 _array에 세팅한다.

_array를 _n + _delta만큼의 크기로 동적 할당한다.

이 두줄의 코드의 시간 복잡도는 Θ(1) 이다.

for(int i = 0; i < _n; i++)
    {
    	_array[i] = array_old[i];
    }

두 번째 코드 블럭이다.

for문을 반복하면서 array_old의 값을 _array에 이전한다.

이 반복문의 시간 복잡도는 Θ(n)이다.

    delete [] array_old;
    return _array;
}

세 번째 코드 블럭이다.

array_old를 삭제한 후 _array를 반환한다.

이 부분의 시간 복잡도는 Θ(1)이다.

 

총 코드의 시간 복잡도는 Θ(1+ n + 1) = Θ(n + 2) = Θ(n)이다.

---

결론

---

함수에 여러 개의 코드 블럭이 있을 때, 시간 복잡도는 가장 차수가 높은 블럭을 따라간다.

가장 큰 블럭이 dominant하다.

때문에 시간 복잡도를 얘기할 때는 가장 dominant한 텀을 잡아서 얘기하는 것이 맞다.