#4-5-3 The Art of Computer Programming - 준수치적 알고리즘

이번절은 유클리드 알고리즘의 분석에 대한 내용이다.

 

일단 유클리드 알고리즘과 연분수와의 관계를 알아본다.

연분수는 계속 분모쪽으로 확장해 나가는 형태이다.

 

유클리드 알고리즘의 최악의 경우를 따져보고

부분몫들의 분포를 구하는 등 알고리즘 분석에 대한 내용이 대부분이다.

 

그래서 내용을 요약하면

유클리드 알고리즘의 최악의 경우는 u,v가 인접한 피보나치 수들일 때 발생한다고 한다.

 

알고리즘 분석은 어렵.. ㅠㅠ