알고리즘

1. Master Theorem- 점화식으로 표현된 재귀알고리즘의 시간 복잡도를 계산할 수 있는 방법중 Master Theorem에 대해 알아보자- Master Theorem은 모든 점화식에 사용이 가능하지 않고 다음 식을 만족하는 점화식 일때만 사용이 가능하다.  - a : 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 , T(n/b) :  부분문제 해결 시간, f(n) : 병합에 필요한 시간 - 이렇게 되면 T(n)의 시간 복잡도를 마스터 정리를 이용하여 구하면 다음과 같다.   - 이 식을 통해 알 수 있는 점은 병합에 걸리는 시간과 부분문제를 해결하는 시간 중에서 더 오래 걸리는 쪽의 영향을 더 많이 받아 시간복잡도가 정해진다는 것이다. 2.Exercise2.1) T(n) = 8 * ..

1. Introduction- 재귀트리(Recursion Tree Method)- 재귀 알고리즘의 Big-Theta를 알아내기 위해서 고안된 직접적인 방법론을 의미한다.- 치환법(Substitution method)로 추측이 불가능 할 때를 의미한다.- 예제를 통해서 한번 자세히 알아보자. 2. Recursion Tree Method2.1. Example 1)- 해당 점화식이 있다고 생각해보자.- 위의 점화식을 다음과 같이 변형하자. - 그후 다음과 같이 재귀트리를 사용하여 계산해보자(n은 4의 거듭제곱 이라고 가정)- 이를 이용하여 전체 시간복잡도를 구해보면 다음과 같다.  2.2)Example2)- 이번엔 계수가 다를 때의 점화식의 시간복잡도를 한번 계산해보자.- 주어진 점화식은 다음과 같다. - 이..

1. Introduction- 분할 정복(DIvide & conquer)알고리즘의 시간복잡도를 구할 수 있는 네가지 방법중 가장 일반적인 "substitution method"에 대해 알아보자.- "substitution method"은 두가지 단계로 구성되어 있다.1)  해당 알고리즘의 시간복잡도를 n에 대한 함수로 가정2)  수학적 귀납법을 사용하여 그 해가 성립하는지 증명하고, 해당 상수를 찾아낸다. 2. Substitution Method- Substitution Method을 사용하면 재귀 알고리즘에서 상한 또는 하한을 설정가능하다(Big-O , Big-Omega)- 해당 방법을 이용하기 위해선 Big-Theta를 증명하려고 하기보단, - Big-O를 먼저 증명하고 그 다음에 Big-Omega를..

1. Review- 분할 정복(Divide & Conquer)중 하나인 Strassen Algorithm에 대해서 알아보자.- 우리는 앞서 4-1 에서 행렬곱을 계산하는 알고리즘에 대해서 알아보았다.- 이때 코드를 다시한번 바라봐보자.A = [[1,2],[3,4]]B = [[5,6],[7,8]]C = [[0,0],[0,0]]for i in range(2): for j in range(2): for k in range(2): C[i][j] += A[i][k]*B[k][j]C------------------------------------------------------[[19, 22], [43, 50]]- 이를 시간 복잡도로 표현하면 O(n^3)과 같다.- 그 이유는 ..