Groups | Search | Server Info | Keyboard shortcuts | Login | Register

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

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

Show all headers | View raw

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

Back to pl.comp.os.linux.programowanie | Previous | Next — Next in thread | Find similar

Thread

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

csiph-web