[Algorytmy] Suma wyrazów ciągu

[80Wieta08]

Witam wszystkich forumowiczów

Mam przed sobą dość ciekawe zadanie, które zafundował nam wykładowca na egzaminie. Otóż mam coś takiego:

Obliczyć za pomocą \(\displaystyle{ o(1)}\) dodawań następującą sumę:
gdzie: n - dana wprowadzania do programu \(\displaystyle{ (n \ge 0)}\)

\(\displaystyle{ 1\\
+1+2\\
+1+2+3\\
+1+2+3+4\\
...\\
+1+2+3+...+n}\)

Wiem jak zadanie ma być zrealizowane od strony informatycznej. I TU właśnie tkwi problem, bo trzeba to zrobić za pomocą jednego konkretnego wzoru.

Tutaj pojawia się moje pytanie do Was: jak się da to obliczyć???

Za wszelką pomoc serdecznie dziękuje
Pozdrawiam.

[norwimaj]

Czy na pewno ma być \(\displaystyle{ o(1)}\) a nie \(\displaystyle{ O(1)}\)? I czy oprócz dodawania można stosować coś jeszcze, na przykład mnożenie?

[80Wieta08]

Chodzi o złożoność obliczeniową czyli \(\displaystyle{ o(1)}\)
Co do drugiego, to wszystkie chwyty dozwolone, byle była tak, a nie inna złożoność obliczeniowa tego algorytmu.

Pozdrawiam.

[norwimaj]

Chodzi o złożoność obliczeniową czyli \(\displaystyle{ o(1)}\)

To bez sensu. Oznacza to że dla bardzo dużych \(\displaystyle{ n}\) program ma działać w zerowym czasie.

[Qń]

Wystarczy skorzystać ze wzorów:
\(\displaystyle{ \sum_{k=1}^nk=\frac{n(n+1)}{2}\\
\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}}\)
Zależnie od gustu - można najpierw zsumować wiersze, a potem kolumny; lub najpierw kolumny a potem wiersze (ja bym wybrał drugą kolejność).

Q.

[norwimaj]

Można też zauważyć że suma jest równa

\(\displaystyle{ \binom23+\binom22+\binom32+\binom42+\ldots+\binom{n+1}2}\),

co od lewej strony się zwija do \(\displaystyle{ \binom{n+2}3}\).

Tak czy siak algorytm jest w czasie stałym, ale nie zerowym.

[Grzesio_]

\(\displaystyle{ {n+3\choose 4}}\)

[80Wieta08]

Przepraszam ze usterkę w temacie. Wybaczcie, ale gościu z którym to mamy jest w innym świecie jak wykłada i rodzą się tego typu problemy.

Chodziło tu oczywiście o \(\displaystyle{ O(1)}\), ale to chyba i tak niczego nie zmieni, prawda ??

Pozdrawiam.

[norwimaj]

Zmieni. \(\displaystyle{ O(1)}\) to jest czas stały. Jeśli dodawanie, mnożenie i dzielenie mamy w czasie stałym, to policzenie

\(\displaystyle{ \binom{n+2}3=\frac{n(n+1)(n+2)}6}\)

zajmie czas stały (\(\displaystyle{ 5}\) operacji), więc takie rozwiązanie powinno być ok.


Grzesio_, napisz pełnym zdaniem bo nie wiem o co chodzi.