Exercise 1) Compute the space complexity for factorial function.
int factorial (int n) { if (n <= 1) return 1; else return n*factorial(n-1); }factorial(n); // 함수 호출
1. paratmeter integer 'n' : 4byte
2. return address : 4byte
=> call 한번당 8byte
위 코드는 recursive function
call 횟수 : n, n-1, n-2, ..., 1 => n번
따라서 S(n) = 8n
Exercise 2) Write the step count table
Exercise 3) Write the step count table
Exercise 4) 다음 알고리즘의 time-complexity를 big-oh 함수로 써라. 여기에서 n = 2^a (즉, 2의 거듭제곱에 해당하는 값으로 가정하라.)
i = 1; => 1번 while (i <= n) { // i = 1,2,3,...,n,n+1 => n+1번 for (k = 1; k <= n; k = k*2) // for loop n번 & k = 1,2,4,...,2^a,2^a+1 -> a+2번 => n*(a+2)번 count++; // n*(a+1)번 i++; // => n번 }n = 2^a
a = log(base2)n
1번 => O(1)
n+1번 => O(n)
n(a+2)번 => O(nlog(base2)n)
n(a+1)번 => O(nlog(base2)n)
n번 => O(n)
=> O(nlog(base2)n)
Exercise 5) 다음 알고리즘의 time-complexity를 big-oh 함수로 써라. (count, i의 초기값은 모두 0)
while (i <= n) { // i = 0,1,2,...,n+1 => n+2번 for (k = i; k <= n; k++) // k : (n+2)(n+3)/2 - 1번 => (n+2)(n+3)/2 - 1번 count++; // => (n+1)(n+2)/2번 i++; // => n+1번 }for (k = i; k <= n; k++)의 경우,
i=0일 때, k=0~(n+1) => n+2
i=1일 때, k=1~(n+1) => n+1
i=2일 때, k=2~(n+1) => n
...
i=n일 때, k=n~(n+1) => 2
=> 2 + 3 + ... + (n+2) => (n+2)(n+3)/2 -1
count++의 경우,
i=0일 때, n+1번
i=1일 때, n번
i=2일 때, n-1번
...
i=n일 때, 1번
=> 1 + 2 + ... + (n+1) => (n+1)(n+2)/2
=> O(n^2)
Exercise 6) Recurrence equation T(n) = 2 T(n/2) + n/2이 주어지고, n = 2^k(k는 0보다 크거나 같은 정수)이며, T(1) = 1이라고 가정하자. T(n)을 전개하여 solving한 결과를 n에 대한 함수로 써라.
풀이)
T(n)
= 2T(n/2) + n/2
= 2(2(T(n/2^2) + n/2^2) + n/2 = 2^2T(n/2^2) + n/2 + n/2
= 2^2(2T(n/2^3) + n/2^3) + n/2 + n/2 = 2^3T(n/2^3) + n/2 + n/2 + n/2
= ...
T(n) = 2^kT(n/2^k) + k*(n/2)
-> T(n) = nT(1)+ log(base2)n*(n/2)
-> T(n) = n + (n/2)log(base2)n
Exercise 7) 4차원의 array x가 다음과 같이 선언되었다.
char x[5][4][3][2];
이 array가 row-major 순서로 저장된다고 가정하자. 한 개의 char를 저장하는데 1byte가 필요하고, x[0][0][0][0]의 시작주소가 0이라 하자. 여기에서, 주소는 byte단위로 할당된다고 가정한다. 즉, row-major 저장순서로 보았을 때 x의 i번째 원소의 주소가 a이면, x의 i+1번째 원소의 주소는 a+1이다. 이때, x[2][3][1][1]의 주소를 써라.
풀이)
x[2][3][1][1] 주소 = 0 + 2x4x3x2 + 3x3x2 + 1x2 + 1 = 48+18+2+1 = 69
Exercise 8) 4차원 array x가 다음과 같이 선언되었다.
char x[5][4][3][2];
이 array가 row-major 순서로 저장된다고 가정하자. 주소가 60이라 할 때, array x의 해당 인덱스 번호를 써라.
0 + ix4x3x2 + jx3x2 + kx2 + l = 60
i=2, j=2, k=0, l=0
x[2][2][0][0]
Exercise 9) Exercise 7,8을 column-major 상황으로 적용하여 답을 구하라.
9-1) x[2][3][1][1] = 0 + 1x5x4x3 + 1x5x4 + 3x5 + 2 = 60+20+15+2 = 97
9-2) 0 + i + 5xj + 5x4xk + 5x4x3xl = 60
l=1, k=0, j=0, i=0
x[0][0][0][1]
