Майстер-теорема (з прикладами)

Зміст

Магістерська теорема
Розв’язаний приклад теореми магістра
Обмеження майстер-теореми

У цьому посібнику ви дізнаєтеся, що таке головна теорема та як вона використовується для розв’язування рекурентних відношень.

Основний метод - це формула для розв’язання рекуррентних відношень виду:

T (n) = aT (n / b) + f (n), де, n = розмір вводу a = кількість підзадач у рекурсії n / b = розмір кожної підпроблеми. Припускається, що всі підзадачі мають однаковий розмір. f (n) = вартість роботи, виконаної поза рекурсивним викликом, що включає вартість поділу проблеми та вартість об'єднання рішень. Тут a ≧ 1 і b> 1 є константами, а f (n) - асимптотично додатним функція.

Асимптотично позитивна функція означає, що для досить великого значення n ми маємо f(n)> 0.

Основна теорема використовується для простого та швидкого розрахунку часової складності відношень рекуррентності (алгоритми поділу та завоювання).

Магістерська теорема

Якщо a ≧ 1і b> 1є константами і f(n)є асимптотично позитивною функцією, то часова складність рекурсивного відношення задається формулою

T (n) = aT (n / b) + f (n) де T (n) має такі асимптотичні межі: 1. Якщо f (n) = O (n ^{log _b a-ϵ} ), то T (n ) = Θ (n ^{log _b a} ). 2. Якщо f (n) = Θ (n ^{log _b a} ), то T (n) = Θ (n ^{log _b a} * log n). 3. Якщо f (n) = Ω (n ^{log _b a + ϵ} ), то T (n) = Θ (f (n)). ϵ> 0 - константа.

Кожну з вищезазначених умов можна інтерпретувати як:

Якщо вартість вирішення підзадач на кожному рівні зросте на певний коефіцієнт, величина f(n)буде поліноміально меншою, ніж . Таким чином, складність часу пригнічується вартістю останнього рівня, тобто.n^{log_b a}n^{log_b a}
Якщо вартість вирішення підзадачі на кожному рівні майже дорівнює, тоді значення f(n)буде . Таким чином, складність часу буде помножена на загальну кількість рівнів, тобто.n^{log_b a}f(n)n^{log_b a} * log n
Якщо вартість вирішення підзадач на кожному рівні зменшиться на певний коефіцієнт, величина f(n)буде поліноміально більшою, ніж . Таким чином, складність часу пригнічується вартістю .n^{log_b a}f(n)

Розв’язаний приклад теореми магістра

T (n) = 3T (n / 2) + n2 Тут a = 3 n / b = n / 2 f (n) = n ² log _b a = log ₂ 3 ≈ 1,58 <2 тобто. f (n) <n ^{log _b a + ϵ} , де, ϵ - константа. Тут випливає випадок 3. Таким чином, T (n) = f (n) = Θ (n ² )