알고리즘 4주차 목요일

오픈북, 텍스북과 슬라이드(PDF로 가지고 있는 사람은 안된다).

Master Theorem 을 어느 정도 주려고 한다.

 

P3는 행렬을 곱하는 방법을 나타내고 있다.

 

 

Divide and Conquer는 시간이 더 오래 걸린다. 똑같은 Subproblem을 계속 해서 풀어서 시간이 오래 걸린다.

 

세타N으로 표현하려면 정확이 N 번 만 실행되어야 하는데 Worst case와 Best case에 해당하는 것처럼 다양하게 되면 빅오를 사용하는 것이 좋다.

Loop 이 있으면 Loop 만 봐도 된다.

Memorization 방식도 Recursion을 하지만 저장하지 않은 부분에 대해서만 call하므로 동일하다.