Рекурсивная функция времени выполнения

Question

1. Дала T(0)=1, T(n)=T([2n/3])+c (в данном случае 2n/3 - нижняя граница). Что такое большой-Θ для T(n)? Это просто log(n)(base 3/2). Скажите, пожалуйста, как получить результат.

2.Given код

void mystery(int n) { 
    if(n < 2) 
     return; 
    else { 
     int i = 0; 
     for(i = 1; i <= 8; i += 2) { 
     mystery(n/3); 
     } 
     int count = 0; 
     for(i = 1; i < n*n; i++) { 
     count = count + 1; 
     } 
    } 
} 

Согласно основной теореме, большой-O граница п^2. Но мой результат - log (n) * n^2 (основание 3). Я не уверен в моем результате, и на самом деле я действительно не знаю, как бороться с временем выполнения рекурсивной функции. Это просто функция журнала?

Или что, если в этом коде T(n)=4*T(n/3)+n^2?

Cheers.

Answer 1

Для (1) рекурсия решается до c log _3/2 n + c.Чтобы убедиться в этом, вы можете использовать метод итераций, чтобы расширить из нескольких условий рецидива и обнаружить закономерность:

Т (п) = Т (2n/3) + с

= T (4n/9) + 2c

= Т (8n/27) + 3c

= Т ((2/3) ^к п) + кс

Предполагая, что Т (1) = c и решение f или выбор к, делает выражение в скобках, равное 1, получаем, что

1 = (2/3) ^к п

(3/2) ^к = п

к = войти _3/2

Подключив в этом выборе к в приведенном выше выражении дает конечный результат.

В (2), то есть рекуррентное соотношение

T (N) = 4T (п/3) + п

Используя теорему мастер с = 4 , b = 3 и d = 2, мы видим, что log _b a = log3 d, поэтому это решается до O (n). Вот один из способов увидеть это. На верхнем уровне вы делаете n работа. На слое ниже этого у вас есть четыре вызова, каждый из которых выполняет n /9 Работает, поэтому вы делаете 4n /9 Работайте, чем верхний слой. Уровень ниже, который делает 16 вызовов, которые каждый делает n /81 Работает в общей сложности 16n /81 Работа, снова много работы, чем слой выше. В целом, каждый слой выполняет экспоненциально меньше работы, чем слой над ним, поэтому верхний слой становится доминирующим над всеми другими асимптотически.

Answer 2

Проделаем анализ сложности, и мы обнаружим, что асимптотическое поведение T(n) зависит от констант рекурсии.

Учитывая T(n) = A T(n*p) + C с A,C>0 и p<1, давайте сначала попытаться доказать T(n)=O(n log n). Мы пытаемся найти D таким образом, что при достаточно больших n

T(n) <= D(n * log(n)) 

Это дает

A * D(n*p * log(n*p)) + C <= D*(n * log(n)) 

Глядя на более высокого порядка, это приводит к

A*D*p <= D 

Итак, если A*p <= 1, это работ и T(n)=O(n log n).

---

В частном случае, A<=1 мы можем сделать лучше, и доказать, что T(n)=O(log n):

T(n) <= D log(n) 

Урожайность

A * D(log(n*p)) + C <= D*(log(n)) 

Глядя на более высокого порядка, это приводит к

A * D * log(n) + C + A * D *log(p) <= D * log(n) 

Что действительно для достаточно больших D и n с A<=1 и log(p)<0.

---

В противном случае, если A*p>1, давайте найдем минимальное значение q такое, что T(n)=O(n^q).Мы пытаемся найти минимальное q такое, что существует D, для которых

T(n) <= D n^q 

Это дает

A * D p^q n^q + C <= D*n^q 

Глядя на более высокого порядка, это приводит к

A*D*p^q <= D 

Минимальный q который удовлетворяет этому, определяется

A*p^q = 1 

Таким образом мы приходим к выводу, что T(n)=O(n^q) для q = - log(A)/log(p).

---

Теперь, учитывая T(n) = A T(n*p) + B n^a + C с A,B,C>0 и p<1, пытаются доказать, что T(n)=O(n^q) для некоторого q. Мы пытаемся найти минимальное q>=a, что для некоторых D>0,

T(n) <= D n^q 

Это дает

A * D n^q p^q + B n^a + C <= D n^q 

Попытка q==a, это будет работать только если

ADp^a + B <= D 

Т.е. T(n)=O(n^a) если Ap^a < 1.

В противном случае мы получаем Ap^q = 1, как и прежде, что означает T(n)=O(n^q) для q = - log(A)/log(p).