Computer Science (26) 썸네일형 리스트형 재귀함수를 이용해서 행렬의 곱 구하기 #include #include void matrix_mul(int** matrix_A, int** matrix_B, int** matrix_C, int len, int i, int j, int k) { /* 행렬의 길이가 2일때 행렬곱 계산하고 종료하기 */ if (len == 2) { matrix_C[i][k] += matrix_A[i][j]* matrix_B[j][k] + matrix_A[i][j + 1]* matrix_B[j + 1][k]; matrix_C[i][k + 1] += matrix_A[i][j]* matrix_B[j][k + 1] + matrix_A[i][j + 1]* matrix_B[j + 1][k + 1]; matrix_C[i + 1][k] += matrix_A[i + 1][j]* .. [C] 시간복잡도가 O(n)인 재귀함수로 피보나치 수열 구하기 앞으로 2학년 때 들었던 자료구조 수업의 내용들을 복습해보려고 한다. 그 학기에 배웠던 여러 과목 중에 가장 어려웠고, 그만큼 중요한 수업이기 때문이다. 오늘은 그 첫 번째로 C언어를 이용해 시간복잡도가 O(n)인 재귀 구조의 피보나치수열을 만들었던 것을 살펴보려고 한다. 1. 시간복잡도가 O(n^2)인 경우 피보나치 수열을 구현하는 방법은 재귀 함수, 반복문 두 가지가 있다. 그중 재귀함수를 이용해 피보나치수열을 구하면 일반적으로 O(n^2)의 시간복잡도를 가진다. long long fib(int n) { if ( n T(n-2) 임으로, 2 이상의 n에 대하여 다음이 성립한다. T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2^2 x T(n -4).... > 2^n/2 x.. 이전 1 2 3 4 다음
