Space complexity & Time complexity
Performance Analysis in Algorithms
Space Complexity
Space complexity is the amount of memory that it needs to run to completion.
total space requirement is S(P)
S(P) = c + Sp(I)
c: fixed space requirements
Sp(I): function of some characteristics of the instance I
In this case, S(I)=0.
It is because of ‘call by address’ in C. Pascal language pass arrays by value and entire array is copied into temporary storage before function is executed.
As a result, S(I)=n.
On the other hand, C pass arrays by pointer which means that passing the address of the first element of the array. It doesn’t need additional memory to keep the array and that’s why the space complexity is 0.
In the recursive function case, complier must save the parameters, the local variables, the return address for each recursive call. Space needed for one recursive call number of bytes required for the 2 parameters and the return address. 4 bytes for pointer list[], 4bytes for integer n, 4bytes for return address.
Assume array has n=MAX_SIZE numbers, m= sum of needed space, total variable space S(MAX_SIZE) is m*n.
It shows that recursive function has bigger overhead than iterative function.
Time complexity
Time complexity is the amount of computer time that it needs to run to completion. T(p) is the sum of its compile time and its execution time. It usually analyzed by ‘count’ variable.
Assume count is 0 as default, tempsum is 2n+3. Specifically, the frequency of for loop is n+1 and the frequency of inner code ‘tempsum += list[i];’ is n. Others run once and it results in 3 times.
How about matrix case that adds tow-dimensional arrays?
Initially count =0 and total count on termination is
2*rows*cols + 2*rows +1
공간 복잡도
공간복잡도란 프로그램을 실행시켜 종료하는데 필요한 메모리 공간의 양을 의미한다. 공간복잡도는 고정공간요구와 가변공간요구의 합으로 결정된다. 고정공간요구란 프로그램의 입출력 횟수, 크기와 관계가 없다. 명령어 공간(코드 저장을 위한 메모리), 변수, 구조체, 상수들을 위한 메모리의 합이다.
가변공간요구란 특정 함수가 순환호출을 할 경우 요구되는 추가 공간을 포함한다. 이 외에도 배열이 함수로 전달되는 방식, 동적할당 크기에 따라 결정된다. 재귀함수의 경우 매 함수 호출마다 매개변수, 지역변수, 복귀주소를 다 기억해야한다. 이 때 추가적인 메모리가 발생한다.
공간 복잡도를 분석할 때는 보통 가변공간요구에 대해서만 고려한다.
리스트에 있는 수를 합산하는 예제이다. 가변공간요구는 배열이 함수로 어떻게 전달되는지에 달렸다. Pascal 같은 유형의 언어는 call by value 방식으로 배열을 전달한다. 이는 함수가 수행되기 전 배열 전체가 메모리에 복사된다는 것을 의미한다. 따라서 가변공간요구 S(I)는 배열의 크기n이 된다.
반면 C언어는 call by value 방식으로 ‘매개변수’를 전달한다. 함수에 배열을 전달할 때 배열의 첫번째 index의 주소(포인터)를 전달한다. 배열을 복사하지 않기 때문에 가변공간요구는 없다. S(I)=0
순환함수의 경우 순환할때마다 매개변수, 지역변수, 복귀주소를 저장해야한다. 따라서 배열의 크기가 n, 필요한 매개변수의 용량을 m이라고 한다면 S(I)=m*n이다.
결국 오버헤드는(간접적인 처리시간, 메모리 등) 순환함수가 훨씬 크다는 것을 알 수 있다.
시간복잡도
시간복잡도는 프로그램에 의해 소요되는 컴파일 시간과 실행 시간을 합한 것이다. 컴파일 시간은 인스턴스 특성에 의존하지 않기 때문에 고정공간요구와 유사하다. 따라서 실행 시간을 중점으로 측정한다.
각 명령문을 수행하는데 독립적인 실행횟수가 필요하므로 count 변수를 사용해 측정한다. 서로 다른 명령문이지만 시간복잡도를 계산할 때는 1개의 count 변수를 이용해 count++ 시키면서 함수의 총 수행횟수를 측정한다. 관건은 반복문, 중첩반복문 등이 얼마나 수행됬는가이다.
하지만 인스턴스 특성에 따라 상수단위까지 시간을 예측하는 것은 어려운 일이다. 따라서 시간 복잡도를 계산할 때는 점근 표기법을 보통 사용한다. 점근 표기법은 빅오(Big-OH), 오메가, 세타 세 가지 종류로 크게 나뉜다. 대표적인 빅오 표기법에 대해서만 설명한다.
모든 n, n≥ n0에 대해 f(n)≤ c*g(n)인 조건을 만족하는 두 양의 상수 c, n0가 존재하면 f(n)=O(g(n))이다.
