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
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
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;
s := s + i*j
END_FOR;
...izvrsavaju 1+2+4+8+...+2^(n-1) puta ?
Hvala