0
알 수없는 알고리즘의 런타임을 모델링하는 반복 관계가 있으며 알고리즘 실행 시간의 하한 또는 상한 및 하한을 찾아야합니다.반복 관계의 점근 분석
사면 거친 형식화하는; Latex-to-image 파서는 이상하게 숫자 식을 사용했습니다. 각 방정식의 수는 숫자가 참조하는 마크 업의 왼쪽 아래 아래이며 입니다.
식 (1)과 (2)는 반복 관계의 부분이다.
방정식 (2)에서 (3)까지를 얻으려면 반복의 몇 반복을 작성하고 형성되는 패턴을 관찰 한 다음 새 변수 k를 사용하여 일반화하십시오.
식 (4)가 참일 때 반복이 중지됨에 유의하십시오.
방정식 (3)에 방정식 (4)를 대입하면 방정식 (5)가됩니다. 또한 로그의베이스 변경 공식을 사용하여 모든 로그를 기본 2 항으로 구하십시오.
식 (5)에서 식 (6)까지 빅 오 분석의 식 (5)에 대한 몇 가지 관찰을 시도합니다. 그러나 솔직히 말해서이 마지막 단계는 내 생각에 불과합니다.
방정식 (5)를 가정하면 은입니다. 방정식 (5)의 세타, 오메가 또는 오 표현은 무엇이며, 가장 중요한 것은 어떻게 증명할 수 있습니까?
제 생각은 n이 매우 커짐에 따라 방정식 (5)의 동작을 알고 싶었습니다. 그러나 n이 무한대에 접근함에 따라 방정식 (5)의 한계는 음수의 로그를 포함하며, 이는 막 다른 길이며, 아마도 잘못된 것입니다.
도움을 주시면 감사하겠습니다.
[master 's theorem] (https://en.wikipedia.org/wiki/Master_theorem)을 사용하여 결과를 얻을 수 있습니다. – AbcAeffchen