그 증거와 함께 마스터 정리에 관한 모든 것!

소개 : 반복 관계를 통해 알고리즘의 시간 복잡도를 찾는 가장 좋은 방법 (바로 가기) / 기술입니다.

출처 : Unsplash를 통한 Jakob Owens

마스터 정리

마스터 정리의 버전은 반복 관계가 다음 형식 인 경우에만 적용됩니다.

작성자 별 이미지
  • 여기서 a ≥ 1, b≥1, d≥ 0

사례 1 : d <log (a) [base b] => 시간 복잡도 = O (n ^ log (a) [base b])

사례 2 : d = log (a) [base b] => 시간 복잡도 = O ((n ^ d) * log (n))

사례 3 : d> log (a) [base b] => 시간 복잡도 = O ((n ^ d))

마스터 정리 증명

위의 마스터 정리 형식은 문제가 트리 형태이고 트리가 아래와 같이 구성되어 있음을 표현합니다.

수준별 문제 구분 (이미지 작성자 : 이미지)

또한 문제가 위와 같이 트리 형태로 표현 될 수 있다면, 그것은 기껏해야 log (n) [base b] 수준까지 올라간다는 것을 알고 있습니다 . 이 수준에서 우리는 1로 남았습니다. 즉, 가능한 가장 짧은 문제로 문제를 나눴습니다.

각 수준에서 수행 된 작업은 다음과 같이 표시됩니다.

각 수준에서 수행되는 작업!

참고 : 위 이미지의 마지막 줄에 수정 사항이 하나 있습니다. "log (b) [base n]"대신 "log (n) [base b]"여야합니다.

마스터 정리의 각 사례를 증명하기 전에 정리해야 할 몇 가지 개념이 있으며 아래에 설명되어 있습니다.

  • 기하학적 시리즈에서 시리즈의 각 다음 요소는 공통 배수 정수만큼 다르므로 일반적으로 "r"로 간주합니다.
  • 기하 급수의 합은 공식이 * ((1-r ^ n) / (1–r))이며 여기서 a는 첫 번째 항입니다.
  • 위의 경우는 트리의 각 후속 수준에서 수행되는 작업이 증가함에 따라 이해할 수 있습니다.
  • 또한 기하학적 계열에서 r <1 인 경우이므로이 경우 주요 항은 최대 효과를 얻을 기하학적 계열의 마지막 항이됩니다.
  • 따라서 총 작업 완료 공식에서 마지막 항만 취합니다. 즉, 시간 복잡도 표현식에서 k = log (n) [base b]를 대체합니다.
해결 된 표현

우리는 이전에 말한 결과를 얻었습니다. 따라서 입증되었습니다.

사례 2의 증거; d = log (b) [base a] :

이는 각 레벨에서 수행되는 작업이 동일하다는 것을 의미하므로 레벨 수각 레벨에서 수행 한 작업을 곱하여 최종 작업을 쉽게 얻을 수 있습니다 .

따라서 입증되었습니다.

사례 3의 증거; d> log (a) [베이스 b] :

즉, 필요한 작업이 후속 수준에서 지속적으로 감소하고 있음을 의미합니다. => 첫 번째 수준에서 수행 한 작업이 최대 값 => 첫 번째 용어 만 고려하면됩니다.

이것은 분명히 O (n ^ d)를 제공합니다.

따라서 입증되었습니다.

여러분이이 기사를 즐겁게 읽고 항상 혼란스러운 마스터 정리의 증거를 쉽게 이해 하셨기를 바랍니다.

Suggested posts

금문교에 대한 완전 무작위 사실

금문교에 대한 완전 무작위 사실

금문교는 세계에서 가장 상징적 인 건축물 중 하나이며, 20 세기에 일어난 가장 인상적인 엔지니어링 업적 중 하나입니다. 1937 년 개통 당시에는 1964 년까지 유지되었던 세계에서 가장 긴 주경간을 가진 현수교가되었습니다.

Go 및 Generics 사용

Go 및 Generics 사용

네, 일어나고 있습니다! Golang에 제네릭을 추가하라는 제안이 수락되었습니다. 이는 향후 일부 버전에서 빈 인터페이스 {}로 복잡한 해결 방법을 사용하지 않고도 일반 솔루션을 코딩 할 수 있음을 의미합니다.

Related posts

새로운 PRNG 설계

새로운 PRNG 설계

Rust는 랜드 크레이트를 위해 더 나은 비 암호화 프로그램이 필요합니다. 이것은 내가 어떻게 하나를 디자인했는지에 대한 설명입니다.

Epsilon-Delta를 사용하여 수학에서 추상적 사고 구축

Epsilon-Delta를 사용하여 수학에서 추상적 사고 구축

눈을 감고 시간을 거슬러 올라가면, 교수가 칠판 옆에 서서 분필로 수학적 정의를 쓰는 동안 뒷줄에 앉아 슬퍼하는 대학생을 봅니다. 클릭, 클릭, 클릭 소리는 교수가 칠판에 글을 쓸 때마다 여전히 분명했습니다.

두 정수를 곱하기위한 Karatsuba 알고리즘

곱셈을위한 분할 및 정복 접근법

두 정수를 곱하기위한 Karatsuba 알고리즘

우리 모두는 어렸을 때 두 숫자를 곱하는 방법을 배웠습니다. (😄)를 잊은 경우에는 두 숫자 19와 95를 곱하는 방법을 살펴 보겠습니다.

수학 방정식 및 연산 시각화

수학 그래프를 사용하여 방정식의 본질을 포착하고 시각적으로 풀기

수학 방정식 및 연산 시각화

방정식의 본질에 대한 시각적 인 조사를 시작하기 전에 방정식은 관계이며 그 관계는 여러 가지 방법으로 기록 될 수 있음을 기억해야합니다. 이 기사 전체에서, 이것은 완전히 새로운 (적어도 나에게는) 사고 방식이기 때문에 오래 전에 배운 오래된 관습을 잊어 버리는 것이 중요합니다.