master-theorem

1열

1답변

사례 -1에 대한 마스터 정리의 증명 :이 단계가 수학적으로 어떻게 유도 되었습니까?

토마스 H. 코먼 (Thomas H. Cormen)의 책을 읽고 마스터 정리 법칙을 이해했습니다. 그러나 다음 사례에서보다 쉬운 수학적 유도를 통해 수학적 증명을 이해하는 데 도움이되는 증명 사례를 보았습니다. 감사 첫 번째 질문에 대한

0열

2답변

반복 관계 : T (n/16) + n log n

마스터 정리를 적용 할 수 있습니까? T (n) = 2T (n/16) + n log n에 대해 마스터 정리는 어떻게 적용하나요? 나는 a = 2, b = 16이되고 나는 c과 k에 대해 확실하지 않습니다.

1열

1답변

런타임 코드 (n) ∈ Θ (n^3/2)

코드 닛을 at (n) ∈ Θ (n^3/2) 런타임과 함께 써야하는 운동을 풀려고합니다. . 루프, if 문, <,>, == 및 if 및 return 문에 대해 반복, 더하기, 빼기, 정수 나누기를 2로 사용할 수 있습니다. t (n) ∈ Θ (n^3)의 런타임을 얻으려면 3 for-loops를 사용해야하며, if 문을 사용하면 런타임이되는 규칙이 있다고

-2열

1답변

마스터 방법을 사용하여 T (n) = 9T (n/3) + 2n^2 + n/3의 시간 복잡도를 해결하는 방법?

f (n)은 무엇인지 알 수 없습니까? 그것은 n^2 또는 2n^2 + n/3입니까? 그런 질문을 해결하는 방법? 다음과 같이 마스터 정리 리콜 미리

1열

2답변

nlog (n) Big Theta (n)입니까? 마스터 정리

Θ (n)의 nlog (n)입니까? Im은 master theorem을 사용하여 reccurrences를 해결하기 때문에 이것을 묻습니다. 방정식이 T (N)가 = 2T (N/2) + n은 N 용액 그것이 T 의미 케이스 (2)를 충족 말한다 로그이다 (N) = Θ는 (N 로그 (N)). n log (n)이 O (n) 일 수있는 방법을 모르겠다. n> 10

2열

1답변

은 Isabelle에서 두 개의 부분 함수가 같은 출력을 생성하지 않는다는 것을 보여주기위한 정의가 필요합니다.

일부 Isabelle 술어를 삭제하기 위해 HOL-Z의 수학 툴킷을 사용하고 있습니다. 특히 나는 부분적인 함수 정의를 사용하여 필자가 작성한 Z 사양에서 관계의 일부를 정의하고있다. 여기서는 간단한 HOL 술어를 생성 할 수 있도록 스키마를 명세서로 변환한다. I 쓸 때 조건부 내에 다음 type_synonym ('a,'b) lts = "('a*'b)

1열

1답변

0 (log^2 (n))의 모든 무거운 동전 찾기

n 개의 동전이 주어 졌다고 가정합니다. 그 중 일부는 무겁고 다른 하나는 불빛입니다. 무거운 동전은 모두 가벼운 동전처럼 무게가 같으며 무거운 동전의 무게는 엄격하게 동전의 무게보다 큽니다. 적어도 하나의 동전은 빛으로 알려져 있습니다. 당신은 잔액이 주어지며, 동전의 서브 세트와 다른 분리 된 서브 세트 동전의 무게를 측정 할 수 있습니다. O (log

0열

1답변

t (n) = 2t (n/2) + n^0.5/logn은 마스터 정리를 사용하여 해결할 수 있습니까?

나는 내 친구와 논쟁이있다. 어제 시험을 치렀다. 나는 그럴 수 없다고 말했고, 그는 1이 될 것이라고 말했다. 아마 맞을지 모르겠다.하지만 나는 이유를 이해하는 것처럼 보인다. 미리 감사드립니다.

0열

1답변

N 전원 n i-e n^n은 다항식입니까? n^2와 n^n 사이에 다항식 차이가 있습니까?

n (i-e n^n)에 대한 n은 다항식입니까? T(n) = 2T(n/2) + n^n 마스터 방법을 사용하여 해결할 수 있습니까?

0열

1답변

마스터 정리 및 지수 함수

최근 마스터 정리 및 정렬에 관한 몇 가지 연습 문제가있었습니다. 일부 표현식의 Θ()를 찾도록 지시했습니다 (Τ (1) = Θ (1)). 대부분은 마스터 정리와 해결되었지만,이 이론의 일반적인 양식을하지 않습니다 이후이 하나 T(n)=T(n^(5/6))+Θ(logn) 분명히, 그렇게 해결되지 않습니다. 어떻게 Θ()를 구합니까?