szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 gru 2016, o 21:34 
Użytkownik

Posty: 7
Lokalizacja: Opole
Witam,
jak policzyć taką sumę bo muszę policzyć złożoność algorytmu i nie wiem jak się prawidłowo za to zabrać:
\sum_{i=1}^{n}  \sum_{j=i+1}^{n}  \sum_{k=1}^{j} 1

Z góry dzięki za odpowiedź.
Góra
Mężczyzna Offline
PostNapisane: 20 gru 2016, o 21:52 
Użytkownik
Avatar użytkownika

Posty: 2343
Lokalizacja: Katowice
Zaczynamy od wewnętrznej sumy: \sum_{k=1}^j 1 = j, ponieważ dodajemy jedynkę j razy. Zatem pozostaje do obliczenia suma \sum_{j=1+i}^n j. Jest to ciąg arytmetyczny o wyrazie początkowym i+1, końcowym n składający się z n-i wyrazów. Zatem:

\sum_{j=i+1}^n\frac{i+1+n}{2}(n-i)

Pozostaje wyznaczyć sumę \sum_{i=1}^{n}\frac{i+1+n}{2}(n-i). Do wyznacznia złożoności obliczeniowej nie musimy wyznaczyć dokładnej wartości tego wyrażenia, ale warto wiedzieć, że suma wielomianu k-tego stopnia jest wielomianem o stopniu o jeden wyższym - w tym wypadku wielomianem trzeciego stopnia.

Natomiast, jeżeli chciałbyś wyznaczyć końcową wartość \frac{1}{3}(n^3-n), możesz wykorzystać następujący fakt:

\sum _{i=1}^{n}i^{2}=\frac {n(n+1)(2n+1)}{6}
Góra
Mężczyzna Offline
PostNapisane: 20 gru 2016, o 22:02 
Użytkownik

Posty: 7
Lokalizacja: Opole
Dzięki za podpowiedź z tym że nie trzeba to liczyć do końca. Tylko nie do końca potrafię wywnioskować skąd właśnie wzięło się to:
\sum_{j=i+1}^n\frac{i+1+n}{2}(n-i)
Jeśli się da prosiłbym o rozpisanie tego bardziej?
Może na jakimś ogólnym przykładzie :/. Lub odesłanie do linka jak się składa takie rzeczy.
Góra
Mężczyzna Offline
PostNapisane: 20 gru 2016, o 22:09 
Użytkownik
Avatar użytkownika

Posty: 2343
Lokalizacja: Katowice
Pamiętasz wzór na sumę ciągu arytmetycznego?
Góra
Mężczyzna Offline
PostNapisane: 20 gru 2016, o 22:26 
Użytkownik

Posty: 7
Lokalizacja: Opole
Aaaa widzę... eh powypadało dużo z głowy. Dzięki wielkie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Sprytne liczenie  winfast29  5
 ''proste liczenie ''  galagala  1
 liczenie średniej - zadanie 3  pbanan  2
 Liczenie czasu.  mpmpmp  1
 Liczenie pierwiastkow  mat-inf  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl