Rozwiąż układ równań rekurencyjnych (zakładając, że N jest potęgą dwójki)
\(\displaystyle{ T(1) = 1}\)
\(\displaystyle{ T(N) = c (\lg N) + T(N/2)}\) dla \(\displaystyle{ N \ge 2}\)
Próbowałem w taki sposób :
\(\displaystyle{ T(N) = c(\lg N) + c(\lg \frac{N}{2}) + c(\lg \frac{N}{4}) + ... + c (\lg 2) + 1}\)
\(\displaystyle{ T(N) = c (\lg (N * \frac{N}{2} * \frac{N}{4} * ... * 2) )+ 1 =
c (\lg ( N^{n} * (\frac{1}{2}) ^{0+1+2+...+n-1} ) + 1}\)
Nie wiem w jaki sposób wyrazić \(\displaystyle{ n}\), a może w ogóle źle do tego podchodzę? Proszę o pomocne wskazówki.
Układ równań rekurencyjnych
-
- Użytkownik
- Posty: 115
- Rejestracja: 9 gru 2007, o 10:07
- Płeć: Mężczyzna
- Lokalizacja: Zamość
- Podziękował: 39 razy
- Pomógł: 7 razy
Układ równań rekurencyjnych
Dokładnie tak - tym bardziej, że prowadzący pod oznaczeniem \(\displaystyle{ \lg}\) rozumie logarytm binarny, a nie dziesiętny.
Temat uważam za zamknięty.
Temat uważam za zamknięty.