Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.os.linux.programowanie > #2159 > unrolled thread

Złożoność obliczeniowa - suma od 2 do n

Back to article view | Back to pl.comp.os.linux.programowanie

Contents

  Złożoność obliczeniowa - suma od 2 do n Szyk Cech <szykcech@spoko.pl> - 2019-03-21 19:10 +0100
    Re: Złożoność obliczeniowa - suma od 2 do n Szyk Cech <szykcech@spoko.pl> - 2019-03-21 19:28 +0100

#2159 — Złożoność obliczeniowa - suma od 2 do n

Witam
Dalej próbuję zrozumieć zawiłości złożoności obliczeniowej algorytmów w 
wydaniu "Wprowadzenie do algorytmów" wydanej przez Pwn w 2017 roku (5 
dodruk do wydania z 2012). Obecnie czytam Dodatek A strona 1170. I 
zaczyna się on stwierdzeniem, że:
∑(j od j=2 do n)(j) - tu (j) jest tym co sumujemy - pierwszy nawias jest 
  warunkami sumy. Ma to rzekomo złożoność Θ(n^2)
Θ - to "duża theta" co znaczy, że algorytm rośnie nie wolniej i nie 
szybciej niż n kwadrat.

Nie potrafię tego zrozumieć!!!

Przecież:
1) Jeśli sumujemy od j=2 do j=n, to mamy n-2 sumowań? Czyli złożoność O(n)
2) Jeśli dodatkowo w każdym kroku sumowania dodajemy do licznika (czyli 
j) 1, to mamy kolejne n-1 sumowań. Czyli O(n)
Czyli: złożoność jest O(2n)=Θ(n) a nie Θ(n^2)

Z drugiej strony jeśli by się uprzeć, to można by się domyśleć kiedy 
złożoność była by Θ(n^2). Ano była by ona taka, gdyby w każdym kroku 
obliczać j od 1 do j, ale wtedy należało by napisać wzór początkowy 
nieco inaczej:
k=∑(j od j=2 do n, k=0)(k += ∑(i=1 do i == j)(i + 1))
Ale jest to nonsens i nawet w podstawówce nikt by tego tak nie obliczał...

Proszę o pomoc w zrozumieniu tego...

pozdro
Szyk Cech

[toc] | [next] | [standalone]

#2160

Ok. Zrozumiałem...
Wynik ∑(j od j=2 do n)(j) jest Θ(n^2), a nie koszt jej obliczenia... Omg...

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.os.linux.programowanie

csiph-web