Mam pewne problemy z rozwiązywaniem relacji powtarzających się.

T (n) = T (n / 2) + log2 (n), T (1) = 1, gdzie n jest mocą 2

To jest problem z pracą domową, więc nie daj mi odpowiedzi. Zastanawiałem się tylko, jak uruchomić problem.

W klasie przeszliśmy twierdzenie mistrza. Ale nie sądzę, aby był to najlepszy sposób na rozwiązanie tej konkretnej relacji.

Naprawdę nie wiem, jak zacząć problem ... powinienem po prostu iść

T(n) = T(n/2) + log_base2(n)
T(n/2) = [T(n/4)+log_base2(n/2)]
T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n)

I po prostu staraj się zdobyć coś, co widzę jako podstawowe równanie?

Odpowiedzi:

2 dla odpowiedzi № 1

To powtarzanie się rozwiązuje Θ ((log n)²). Oto dwa sposoby, aby to zobaczyć.

Jeśli wiesz, że n jest idealną mocą dwóch (to znaczy n = 2^k), możesz przepisać powtarzanie jako

T (2^k) = T (2^k-1) + k

Zdefiniujmy nowy cykl S (k) = T (2^k). Wtedy to rozumiemy

S (k) = S (k - 1) + k

Jeśli rozszerzymy ten okres, otrzymamy to

S (k) = S (k - 1) + k

= S (k - 2) + (k - 1) + k

= S (k - 3) + (k - 2) + (k - 1) + k

= S (k - 4) + (k - 3) + (k - 2) + (k - 1) + k

...

= S (0) + 1 + 2 + 3 + ... + k

= S (0) + Θ (k²)

Zakładając S (0) = 1, to rekurencja rozwiązuje się do Θ (k²).

Ponieważ S (k) = T (2^k) = T (n), otrzymujemy, że T (n) = Θ (k²) = Θ (log² n).

Iterating the Recurrence

Inną opcją jest rozwinięcie kilku warunków powtarzania i sprawdzenie, czy pojawią się jakieś ładne wzorce. Oto co otrzymujemy:

T (n) = T (n / 2) + lg n

= T (n / 4) + lg (n / 2) + lg n

= T (n / 8) + lg (n / 4) + lg (n / 2) + lg n

...

W końcu, po warstwach lg n, ta rekurencja przestaje działać i pozostajemy z tym wyrażeniem:

lg n + lg (n / 2) + lg (n / 4) + ... + lg (n / 2^{lg n)}

Używając właściwości logarytmów, możemy przepisać to jako

lg n + (lg n - 1) + (lg n - 2) + (lg n - 3) + ... + (lg n - lg n)

Lub, odwrotnie, jest to suma

0 + 1 + 2 + 3 + ... + lg n

Suma ta to suma Gaussa do lg n, która ocenia na (lg n) (lg n + 1) / 2 = Θ ((log n) 2</ sup>).

Mam nadzieję że to pomoże!

---

1 dla odpowiedzi nr 2

Jeśli n jest potęgą 2, możesz po prostu rozwinąć rekurencję i rozwiązać dokładnie, używając lg (a / b) = lg (a) - lg (b).

T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1) + 1
= (lg(n) - 0) + (lg(n) - 1) .... + (lg(n) - lg(n)) + 1
= lg(n)*lg(n) - lg(n)*(lg(n)+1)/2 + 1
= lg(n)*lg(n)/2 - lg(n)/2 + 1

---

0 dla odpowiedzi № 3

Można to zrobić za pomocą twierdzenia Akra-Bazzi. Zobacz trzeci przykład w http://people.mpi-inf.mpg.de/~mehlhorn/DatAlg2008/NewMasterTheorem.pdf.

---

0 dla odpowiedzi nr 4

Można to rozwiązać za pomocą Twierdzenie mistrza. Twój a=1 i b=2 i f(n) = log(n). Następnie c = log2(1) = 0. Z powodu twojego c i f(n) wpadniesz w drugi przypadek (gdzie k=1).

Więc rozwiązaniem jest Θ (log² n)

---