[Teoria złożoności] orginalny współczynnik b

[lightinside]

Mam pytanie jak zastosować twierdzenie o rekurencji uniwersalnej w tym przypadku:
(uwaga przykład jest z głowy, ale oddaje problematykę, (znaczy spotkałam się z przykładem zawierającym tę trudność i nie wiedziałam co zrobić))


\(\displaystyle{ T(n)=T(n-1)+ \frac{n}{2} -n}\)

Za a podstawiłam 1 a co powinam podstawić za b?

[bartek118]

Przecież to nie jest przykład na zastosowanie tego twierdzenia.

[Chromosom]

\(\displaystyle{ T(n)=T(n-1)+\frac n2-\frac{2n}2\\ T(n)=T(n-1)-\frac n2}\)

Teraz można zastosować funkcje tworzące, albo podstawiać kolejne wyrazy:

\(\displaystyle{ T(n-1)=T(n-2)-\frac{n-1}{2}\\ T(n-2)=T(n-3)-\frac{n-2}{2}\\ T(n)=T(n-2)-\frac{n-1}{2}-\frac n2\\ T(n)=T(n-3)-\frac{n-2}{2}-\frac{n-1}{2}-\frac n2\\ \ldots\\ T(n)=T(n-k)-\frac{n-k+1}{2}-\frac{n-k+2}{2}-\,\ldots\,-\frac n2}\)

Niech teraz \(\displaystyle{ k=n}\), wtedy:

\(\displaystyle{ T(n)=T(0)-\frac12-\frac22-\frac32-\,\ldots-\frac n2\\ T(n)=T(0)-\frac12\left(1+2+3+\,\ldots\,+n\right)}\)

\(\displaystyle{ T(0)}\) jest nieistotną stałą, natomiast w nawiasie znajduje się suma ciągu arytmetycznego. Złożoność obliczeniowa jest ujemna poczynając od pewnego \(\displaystyle{ n}\), sprawdź zatem, czy dobrze przepisałaś zadanie

Twierdzenie o rekurencji uniwersalnej można wyprowadzić w podobny sposób, jak pokazałem powyżej, chociaż oczywiście w niektórych miejscach jest to bardziej skomplikowane. Proponuję Ci to jako ćwiczenie. Pamiętaj, że twierdzenia tego nie stosuje się w tym zadaniu. Ogólnie: jeśli złożoność obliczeniowa jest określona w postaci \(\displaystyle{ T(n)=T(n-1)+\,\ldots}\) lub podobnej, powinnaś próbować rozwiązać je tak, jak powyżej.

[lightinside]

bartek118

Był w zadaniach o tym twierdzeniu a ja dużo chorowałam i poprostu o tym nie wiedziałam (O tym co chromosom napisał) Umiałam zwykłą że tak powiem i to twierdzenie bez jakiś eee innych rzeczy...

Chromosom

Dzięki wieczorem to ogarnę

[lightinside]

Hej czy czasem zamiast:

\(\displaystyle{ T(n-2)=T(n-3)- \frac{n-2}{3}}\)

Nie powinno by tak: ???

\(\displaystyle{ T(n-2)=T(n-3)- \frac{n-2}{2}}\)

Złożoność obliczeniowa jest ujemna poczynając od pewnego n, sprawdź zatem, czy dobrze przepisałaś zadanie

Napisałam że liczby wziełam z nieba możesz podac jakieś przykłady do obliczeń?

chętnie pocwiczę mimo że to raczej proste

Czy takie zadanie zrobiłam dobrze?

\(\displaystyle{ t(n)=T(n-1)+ \frac{n ^{2} }{3}}\)
\(\displaystyle{ t(n-1)=T(n-2)+ \frac{n ^{2}-1 }{3}}\)
\(\displaystyle{ t(n-2)=T(n-3)+ \frac{n ^{2}-2 }{3}}\)

\(\displaystyle{ t(n)=T(n-2)+ \frac{n ^{2}-1 }{3}+ \frac{n ^{2} }{3}}\)

\(\displaystyle{ t(n)=T(n-3)+ \frac{n ^{2}-2 }{3} + \frac{n ^{2}-1 }{3}+ \frac{n ^{2} }{3}}\)

Następnie

\(\displaystyle{ T(n)=T(n-k)+ \frac{n^2-k+1}{3} + \frac{n^2-k+2}{3} +...+ \frac{n^2}{3}}\)

Niech n=k

\(\displaystyle{ T(n)=T(0)+ \frac{n^2}{3} \left( -k+1-k+2+...+1\right)}\)

[Chromosom]

Poprawiłem. Przykład:

\(\displaystyle{ a_n=a_{n-1}+n-2}\)

Spróbuj samodzielnie

W podanym zadaniu musisz podstawić \(\displaystyle{ n-1}\) w miejscu \(\displaystyle{ n}\), czyli w ułamku powinno być \(\displaystyle{ (n-1)^2}\).

[lightinside]

Twój przykład:

wyszło mi

\(\displaystyle{ T(n)=a_0 -1+...+n-2}\)

Co dalej z tym?

ewentualnie gdybysmy bardzie rozwineli to by było:

\(\displaystyle{ T(n)=a_0 - 3 - 2 - 1+...+n-2}\) (o ile dobrze licze w pamieci)

Mój przykład:

\(\displaystyle{ T(n)=T(n-k)+ \frac{\left( n-k+1\right) ^2}{3} + \frac{\left( n-k+2\right) ^2}{3} +...+ \frac{ n^2}{3}}\)

[Chromosom]

Pierwsze rozwinięcie jest niemal poprawne - powinno kończyć się na \(\displaystyle{ n-2}\). Zastosuj wzór na sumę wyrazów ciągu arytmetycznego

[lightinside]

A no tak źle przepisałam bo w zeszycie tak mam;) to updatuje to zaraz.

Myślisz że pamiętam? muszę sobie przypomniec...

A mój przykład? Teraz dobrze poprawiony?

Masz na myśli ten wzór?

\(\displaystyle{ \frac{a_1 + a_n}{2} \cdot n}\)

czyli:

\(\displaystyle{ \frac{\left( a_0- 1+...+ n-2\right) + \left( a_0-1\right) }{2} \cdot n}\)

???

[Chromosom]

Twój przykład jest teraz rozwiązany poprawnie.

Wzór jest poprawny, tylko zastosowanie już nie; wyraz \(\displaystyle{ a_0}\) powinien znaleźć się obok. Musisz zastosować wzór dla liczb \(\displaystyle{ -1+0+1+2+\,\cdots\,+n-2}\)

[lightinside]

Znaczy wyłączyc to przed nawias? znaczy \(\displaystyle{ a_0}\)

[Chromosom]

Zgadza się.

Co do Twojego zadania, będzie potrzebny wzór na sumę kwadratów kolejnych liczb naturalnych. Istnieje kilka sposobów. Proponuję funkcje tworzące.

[lightinside]

\(\displaystyle{ S= \frac{a_0\left( -1+...+n-2+n-2\right) }{2} \cdot n}\)

To się zgadza?

[Chromosom]

Nie możesz wyłączyć \(\displaystyle{ a_0}\) przed nawias jako czynnik - nie jest to wspólny czynnik. Możesz je wyłączyć jako składnik:

\(\displaystyle{ T(n)=a_0-1+0+1+2+\,\cdots\,+n-2=a_0+\bigl(-1+0+1+2+\,\cdots\,+n-2\bigr)=a_0+\frac{-1+(n-2)}{2}\cdot n}\)

[lightinside]

Powiem tak nie zabardzo rozumiem bo tam jest \(\displaystyle{ a_0}\) dodac \(\displaystyle{ a_1}\)

a \(\displaystyle{ a_1}\) to:

\(\displaystyle{ a_1=a_0-1}\)