때 우리는 문제를 해결하고 할 때 많은 방법으로 사용할 수 있는 그 문제를 해결하기 위해(예를 들어 매트릭스 체인의 곱셈 문제),그 시간에 알고리즘의 분석이 필요합니다.

알고리즘의 분석은 점근 적 의미에서 복잡성을 추정하는 것을 의미합니다. “알고리즘 분석”이라는 용어는 Donald Knuth 에 의해 만들어졌습니다. 알고리즘의 분석은 그것을 실행하는 데 필요한 시간과 공간 자원의 양을 결정하는 것입니다.

알고리즘의 대부분은 본질적으로 재귀 적이며 분할 및 정복 전략을 사용합니다. 재귀 알고리즘은 다른 입력에 대해 자체를 호출합니다. 일반적으로 원래 입력의 일부이지만 크기가 작습니다(하위 문제). 재발 관계를 해결하는 방법은 많습니다. 그들은 다음과 같습니다:

1. 마스터 정리

2. 재발 트리 방법

3. 대체 방법

4. 수의 변화 방법

사이에서 이러한 모든 방법을 마스터 정리의 가장 빠른 방법을 찾기 위해 시간의 복잡성은 기능이다. 그것은 매우 이해하기 쉽고 적용하기 쉽습니다. 우리는 단지 몇 가지 경우를 기억해야합니다. 그래서 여기에 우리가 간다.