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

[Chromosom]

\(\displaystyle{ a_1}\) symbolizuje pierwszy wyraz ciągu arytmetycznego, któego sumę chcesz obliczyć. Nie jest to \(\displaystyle{ a_1}\) rozumiane jako \(\displaystyle{ T(1)}\) Liczba \(\displaystyle{ a_0}\) jest nieznana i w związku z tym musi znaleźć się poza nawiasem.

Można by też napisać: \(\displaystyle{ S_n=\frac{b_1+b_n}{2}\cdot n}\), i jako \(\displaystyle{ b_1}\) podstawić \(\displaystyle{ -1}\) - czyli pierwszy wyraz ciągu arytmetycznego, którego suma jest obliczana.

[lightinside]

Zaraz do tego wróce

Czy to jest dobry wzór?:

\(\displaystyle{ \sum_{i=0}^{n} \frac{\left( n-k+i\right)^2 }{3}}\)

właśnie próbowałam to wyliczyc

Ale skąd wiesz że \(\displaystyle{ a_1 = -1}\) ?

[Chromosom]

Wzór jest poprawny, teraz musisz podstawić \(\displaystyle{ k=n}\).

Dlaczego \(\displaystyle{ a_1=-1}\)? Widać to tutaj:

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

[lightinside]

Dobra czyli innymi słowy bierzesz pierwszy wyraz wolny i ostatni tak? (bo dla \(\displaystyle{ n}\) tak?)

[Chromosom]

Zgadza się. \(\displaystyle{ a_0}\) tak naprawdę w teorii złożoności obliczeniowej nie jest istotne ponieważ jest wyrazem stałym.

[lightinside]

Dobrze ja mam takie głupie pytanie aczkolwiek ważne

Co My właściwie robimy? wiem że obliczamy złożonośc obliczeniową ale jakiego przypadku? jak ten typ się nazywa?

I pokoleji?

rozpisujemy \(\displaystyle{ t(n)}\) tak aby móc wejśc na przypadek ogólny

A co robimy właściwie potem? i po co?

Co dalej jak już mamy tą sume to już koniec?

Niech \(\displaystyle{ n=k}\)
\(\displaystyle{ \sum_{i=0}^{n} \frac{i^2}{3}}\)

[Chromosom]

Jest to rekurencja liniowa pierwszego rzędu. Można ją zastosować w następującym przypadku: zależy nam na wyznaczeniu złożoności obliczeniowej pewnego algorytmu działającego rekurencyjnie. Nie jest ważne, jaki jest to algorytm - wiemy jednak, że jego \(\displaystyle{ n}\)-ty obieg zajmuje czas \(\displaystyle{ n}\). Można stąd wyciągnąć wniosek, że całkowity czas działania algorytmu jest sumą \(\displaystyle{ n}\)-tego obiegu oraz pozostałych \(\displaystyle{ n-1}\) obiegów, co zapiszemy jako \(\displaystyle{ T(n)=T(n-1)+n}\). Jest to inny przykład, niż ten, który rozważaliśmy poprzednio.

Następnie kolejno rozpisujemy wzór, tak aby móc zaobserwować, jaka jest zależność dla dowolnego \(\displaystyle{ k}\). Podstawiamy \(\displaystyle{ n=k}\) i uzyskujemy wzór ogólny \(\displaystyle{ T(n)}\). Jest to jedna z metod uzyskania powyższego wyniku.

Suma może, ale nie musi być końcowym etapem obliczeń. Najczęściej próbujemy zapisać algorytm w prostszej postaci - za pomocą notacji \(\displaystyle{ O}\). Można tego dokonać następująco:

\(\displaystyle{ \frac{n(n-3)}{2}\\ \\ 0<\frac{n(n-3)}{2}\le cn^2}\)

Można zaobserwować, że wystarczy dobrać \(\displaystyle{ c=1}\), aby prawa strona nierówności przy odpowiednio dużych \(\displaystyle{ n}\) (a w tym przypadku nawet przy wszystkich) była większa, niż jej lewa strona.

W kwestii sumy: czynnik \(\displaystyle{ \frac13}\) nie jest istotny - można go wyłączyć przed sumę. Jako metodę pozwalającą na obliczenie szukanej sumy proponuję zastosowanie funkcji tworzących. Istnieje również kilka innych metod, np. sumowanie przez części lub zaburzanie.

[lightinside]

Dobra daj zaburzanie bo fajnie brzmi

Na czym ono polega?

Czyli rozumiem że algorytmy rekurencyjne do których stosuje Twierdzenie o rekurencji uniwersalnej, mogę też wyliczy ich złożonośc za pomocą tej metody?

[Chromosom]

Jeśli chodzi o twierdzenie o rekurencji uniwersalnej, również można zastosować podobną metodę, chociaż postępowanie jest nieco inne.

Zaburzanie w tym zadaniu wygląda tak: wybieramy szereg, który będzie sumować liczby podniesione do potęgi o 1 większej, niż rozważana w zadaniu - czyli do trzeciej potęgi:

\(\displaystyle{ \sum\limits^n_{k=0}(k+1)^3=(n+1)^3+\sum\limits^{n-1}_{k=0}(k+1)^3}\)

Szereg znajdujący się po prawej stronie można przepisać następująco:

\(\displaystyle{ \sum\limits^n_{k=0}(k+1)^3=(n+1)^3+\sum\limits^{n}_{k=0}k^3}\)

Stąd otrzymujemy następujący wynik:

\(\displaystyle{ (n+1)^3=\sum\limits^n_{k=0}\left((k+1)^3-k^3\right)\\ \\ (n+1)^3=\sum\limits^n_{k=0}\left(k^3+3k^2+3k+1-k^3\right)\\ \\(n+1)^3=\sum\limits^n_{k=0}\left(3k^2+3k+1\right)\\ (n+1)^3=3\sum\limits^n_{k=0}k^2+3\sum\limits^n_{k=0}k+\sum\limits^n_{k=0}1}\)

Ostatni szereg oznacza, że dodajemy jedynkę \(\displaystyle{ n+1}\) razy. Stąd wynika następująca równość:

\(\displaystyle{ 3\sum\limits^n_{k=0}k^2=(n+1)^3-3\sum\limits^n_{k=0}k-\sum\limits^n_{k=0}1\\ \\ 3\sum\limits^n_{k=0}k^2=(n+1)^3-3\cdot\frac{n(n+1)}{2}-(n+1)}\)

Następnie należy uprościć wyrażenie znajdujące się po prawej stronie i podzielić równanie stronami przez 3. Na początku upraszczania warto wyłączyć przed nawias czynnik \(\displaystyle{ \frac{n+1}{2}}\).

[lightinside]

Dlaczego to jest sobie równe?

\(\displaystyle{ \left( n+1\right) ^3+ \sum_{k=0}^{n-1} \left( k+1\right) ^3}\)

\(\displaystyle{ \left( n+1\right) ^3+ \sum_{k=0}^{n}k^3}\)

gdybyśmy mieli tam \(\displaystyle{ 2}\) w nawiasie to by nam została \(\displaystyle{ 1}\) ?

[bartek118]

Rozpisz te sumy - to jest dokładnie to samo.