[es] - Par problema iz analize slozenosti programa

anon315

Član broj: 315
Poruke: 1657
*.sab.sezampro.yu

+13 Profil

Par problema iz analize slozenosti programa

^{10.03.2004. u 17:19 - pre 245 meseci}

Hello,

evo dođoh do analize složenosti pa mi treba malo pomoći u samom početku.

Problem 1:

Treba naći red funkcije složenosti priloženog potprograma ako se pretpostavlja da ispisivanje jednog znaka traje isto kao izvršavanje deset naredbi u operativnoj memoriji.

Code:

1  PROCEDURE strlen (n: IN CARDINAL);
2      LOCAL korak,nzvez,i,j: CARDINAL;
3               znak: CHARACTER;
4      korak := 1;
5      znak := 'nabla'
6      nzvez := 0;
7      i := 1;
8      WHILE i <= 3 * n DO
9          nzvez := nzvez + korak;
10         WRITE (znak, j := 1, 3*n),
11               ('*',  j := 1, znvez)
12         IF i = n               THEN
13           znak := '*'
14         ORIF i = 3 * n / 2 + 1 THEN
15           korak := -1
16         ORIF i = 2 * n         THEN
17           znak = 'nabla'
18         END_IF;
19         i := i + 1
20     END_WHILE;
21 END_PROCEDURE

Sad redom od 4 do 21 dajem broj instrukcija:

1, 1, 1, 1, 3n+1, 3n, (3n*10)*3n, [1+2+...+3n/2+(3n/2+1)+3n/2+...+2+1]*10, 3n, 1, 3n-1, 1, 3n-2, 1, 0, 3n, 0, 1.

Problematična mi je linija 11 (crveno). Nemam predstavu kako da dobijem to. Potrebno detaljno objašnjenje.

Problem 2:

Code:

BEGIN
  k := 1;
  s := 0;
  FOR i :=1 TO n DO
      FOR j := 1 TO k DO
          s := s + i*j
      END_FOR;
      k := k+k
  END_FOR
END

Zašto se linije...

Code:

s := s + i*j
END_FOR;

...izvrsavaju 1+2+4+8+...+2^(n-1) puta ?

Hvala

Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.dialup.neobee.net.

Sajt: www.novikorisnik.net

+5 Profil

Re: Par problema iz analize slozenosti programa

^{10.03.2004. u 20:50 - pre 245 meseci}

Prvo odgovor na drugo (mada mi nije jasno šta tu nije jasno):
"Zašto se linije...
...izvrsavaju 1+2+4+8+...+2^(n-1) puta ?"
- Zato što su u FOR petlji od 1 do k, a brojevi 1,2,4,... 2^(n-1) su upravo vrednosti koje ima promenljiva k - ona menja vrednost nakon te petlje:
k:=k+k
pri svakom pokretanju unutrašnje petlje k ima vrednost 2^(i-1).

Za prvi zadatak je problematična linija 14 jer zavisi od parnosti parametra procedure. Naime, ukoliko je n neparano, uslov nikada neće biti zadovoljen pa neće doći ni do promene promenljive korak. To direktno dovodi u pitanje kalkulaciju linije 11 jer se radi o ispisu nzvez zvezdica, a nzvez se menja u svakom koraku za vrednost promenljive korak.

Računica je skoro ispravna za parne vrednosti parametra n.

Da objasnim zašto je cifra za liniju 11 skoro ona izvučena crvenom:
Radi se instrukciji za pisanje - zato se izraz na kraju množi sa 10.
Šta se radi u liniji 11? Ispisuje se nzvez karaktera '*'. Dakle, u nekom prolazu WHILE petlje to uzima nzvez * 10 instrukcija.
Koje vrednosti uzima promenljiva nzvez tokom ovih 3n ciklusa? Kreće od 0 i u liniji 9 se sabira sa promenljivom korak i tako dobija vrednost 1 i tako dolazi do linije 11. Pri svakom sledećem koraku nzvez se povećava za 1 (zato što korak ima vrednost 1) u liniji 9 - sve do momenta dok se ne izvrši instrukcija na liniji 15. U tom momentu nzvez ima vrednost isto koliko i i: 3n/2+1. Instrukcija na liniji 15 menja vrednost promenljive korak na -1, što praktično znači da će u svim narednim koracima na liniji broj 9 nzvez da umanjuje svoju vrednost za 1. Takvih koraka je 3n/2-1, pa će u poslednjem prolazu nzvez dobiti vrednost 2 (a ne 1, kako piše u crvenoj računici).

Linija 10:
Promenljiva znak inicijalno ima vrednost 'nabla', što znači da nosi 5 karaktera, na liniji 10 za ispis ide 5*10*3n instrukcija. Ovo se ponavlja n puta, kada postaje zadovoljen uslov linije 12 pa se izvršava instrukcija linije 13 - znak postaje '*' (1 karakter). U sledećih n ciklusa je broj instrukcija po ciklusu 10*3n. Tada se zadovoljava uslov linije 16 i izvršava instrukcija na liniji 17 - znak ponovo postaje 'nabla' (5 karaktera). Do kraja će linija 10 još n puta izvršiti 5*10*3n instrukcija. Sabiranjem se ukupno za liniju 10 dobija 11*10*3n instrukcija.

Šta se menja ako je parametar n neparan?
- uslov linije 14 nikad neće biti zadovoljen, pa se instrukcija linije 15 neće ni jednom izvršiti, ali će se zato uslov na liniji 16 ispitivati 3n-1 umesto 3n-2 puta.
- kako instrukcija linije 15 neće biti ispunjena, to će nzvez u liniji 9 da raste za 1 pri svakoj iteraciji WHILE petlje, što u liniji 11 daje potpuno drugačiju kalkulaciju: [1+2+...+3n]*10.

Ne znam o kom se programskom jeziku radi, pa sam ovu analizu radio na osnovu nekih pretpostavki, naročito o funkciji WRITE.

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Odgovor na temu