Algorytmy - "fragment programu"

spec_u
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 17 lis 2007, o 18:45
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 5 razy
Pomógł: 1 raz

Algorytmy - "fragment programu"

Post autor: spec_u »

Dany jest fragment programu:

Kod: Zaznacz cały

for i:= 1 to n-1 do
begin

     for j:= i + 1 to n do
     begin
                 OPERACJA DOMINUJACA
     end
end  
a) Ile razy wykona sie operacja dominująca, jeżeli n=2150 ?
b) Oszacuj czasową złożoność obliczeniową programu w notacji "dużego 0".

Prosze o pomoc w zadaniu
Goter
Użytkownik
Użytkownik
Posty: 293
Rejestracja: 22 lis 2008, o 18:11
Płeć: Mężczyzna
Lokalizacja: Białystok
Podziękował: 5 razy
Pomógł: 85 razy

Algorytmy - "fragment programu"

Post autor: Goter »

a) 2150 * 2149 / 2 = 2310175
b) O(n^2)
spec_u
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 17 lis 2007, o 18:45
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 5 razy
Pomógł: 1 raz

Algorytmy - "fragment programu"

Post autor: spec_u »

Goter dlaczego w a) dzielimy przez 2 ?
matshadow
Użytkownik
Użytkownik
Posty: 941
Rejestracja: 17 gru 2007, o 21:48
Płeć: Mężczyzna
Lokalizacja: Kingdom Hearts
Podziękował: 6 razy
Pomógł: 222 razy

Algorytmy - "fragment programu"

Post autor: matshadow »

bo jest to wzór na sumę ciągu arytmetycznego W tym przypadku:
\(\displaystyle{ S_{n-1}=\frac{a_1+a_{n-1}}{2}\cdot (n-1)}\)
spec_u
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 17 lis 2007, o 18:45
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 5 razy
Pomógł: 1 raz

Algorytmy - "fragment programu"

Post autor: spec_u »

to jeszcze może jakby ktoś wytłumaczył dlaczego złożoność tego programu będzie kwadratowa ?

"O(n^2)"
Awatar użytkownika
wafello
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 7 sty 2009, o 21:50
Płeć: Mężczyzna
Lokalizacja: Józefina
Pomógł: 6 razy

Algorytmy - "fragment programu"

Post autor: wafello »

Ponieważ wzór dokładny na ilość operacji:
n * (n-1) / 2
po odrzuceniu stałych
n*n
matshadow
Użytkownik
Użytkownik
Posty: 941
Rejestracja: 17 gru 2007, o 21:48
Płeć: Mężczyzna
Lokalizacja: Kingdom Hearts
Podziękował: 6 razy
Pomógł: 222 razy

Algorytmy - "fragment programu"

Post autor: matshadow »

ja to rozumiem tak, że for w forze to O(n^2), for w forze w forze to O(n^3) itd
Awatar użytkownika
wafello
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 7 sty 2009, o 21:50
Płeć: Mężczyzna
Lokalizacja: Józefina
Pomógł: 6 razy

Algorytmy - "fragment programu"

Post autor: wafello »

O ile każdy for będzie wykonywany n razy - Tak.
ODPOWIEDZ