Analiza costurilor si timpul de executie pentru problemele din capitolul 5

Problema nr 1.OperatieCost Nr. repetari

1.11

2.11

3.2(n+1)1

4.12(n+1)

5.1T1(n)

6.1T1(n)

7.11

8.1T2(n)

T = 3 + 4(n+1) + 2T1(n) + T2(n)Problema nr 2.OperatieCostNr. repetari

1.11

2.2(n+1)1

3.12(n+1)

4.1T1(n)

5.1T1(n)

T = 1 + 4(n+1) + 2T1(n)Problema nr 3.OperatieCostNr. repetari

1.11

2.2(n+1)1

3.1T1(n)

4.11

5.1T2(n)

6.1T3(n)

T = 2 + 2(n+1) + T1(n) + T2(n) + T3(n)

Problema nr 4.OperatieCostNr.r epetari

1.11

2.11

3.1T1(n)

4.1T1(n)

5.1T1(n)

6.2(n+1)1

7.11

8.11

9.2(n+1)1

10.1T2(n)

T = 4 + 3T1(n) + 4(n+1) + T2(n)

Problema nr 5.OperatieCostNr. repetari

1.11

2.11

3.1T1(n)

4.1T1(n)

5.1T1(n)

6.2(n+1)1

7.11

8.2n1

9.2(n-i)n-1

10.1n(n-i-1)

11.1T2(n)

T = 3 + 3t1(n) + 2(n+1) + 2(n-1)(n-i) + 2n + n(n-i-1)

Problema nr 6.OperatieCostNr. repetari

1.2n1

2.1n-1

3.2(n+1)n-1

4.1n*(n-1)

5.2(n-j)T1(n)

6.1T1(n)*(n-j-1)

7.1T1(n)*(n-j-1)

8.1T2(n)

T = 2n + (n-1)(2n+3) + n*(n-1) + T1(n) + 2T1(n)* (n-j-1) + T2(n)Problemele 7-10.OperatieCostNr. repetari

1.11

2.11

3.1T1(n)

4.11

5.2(n+1)T2(n)

6.1T2(n)

7.11

8.2(n+1)1

9.1n

10.1n*n

11.1T3(n)

12.11

132(n+1)1

14.2(n+1)n

15.1n*n

16.11

17.2(n+1)1

18.1n

19.2(n+1)n

20.1n*n

21.1n

22.1T4(n)

23.1T4(n)

24.1T4(n)

25.1n

26.1T5(n)

27.1T5(n)

T = 6 + T1(n) + (2n+3)T2(n) + 2(n+1) + n(n+1) + T3(n) + 4(n+1)(n+1) + 2n*n + 3n + 3T4(n) + 2T5(n)

Problema nr 11.OperatieCostNr. Repetari

1.11

2.2(m+1)1

3.1m

4.2(n+1)m

5.1m*n

6.1T1(mn)

7.11

8.1T2(n)

T = 2 + 2(m+1) + m(2n+3) + m*n + T1(mn) + T2(n)

Problema nr 12.OperatieCostNr. repetari

1.11

2.2(m+1)1

3.1m

4.2(n+1)m

5.1m*n

6.1T1(n)

7.1m

8.1T2(m)

9.1T2(m)

T = 1 + 2(m+1) + 2m + 2m(n+1) + m*n + T1(n) + 2T2(m)

Problema nr 13.OperatieCostNr. repetari

1.11

2.2(n+1)1

3.1n

4.2(m+1)n

5.1m*n

6.1T1(m)

7.1n

8.1T2(n)

9.1T2(n)

T = 1 + 2(n+1) + 2n + m*n + 2n(m+1) + T1(m) + 2T2(n)Problema nr 14.OperatieCostNr. repetari

1.11

2.11

3.11

4.2(m+1)1

5.2(p+1)m

6.1m*p

7.2(n+1)m*p

8.1m*p*n

T = 3 + 2(m+1) +2m(p+1) + m*p + 2mp(n+1) + m*p*nProblema nr 15.OperatieCostNr. repetari

1.2(m+1)1

2.2(m+1)m

3.1m*m

4.1T1(m)

5.1T2(m)

6.2(p+1)1

7.2(m+1)p

8.2(m+1)p*m

9.1p*m*m

10.2(m+1)p

11.1p*m

12.2(m+1)p

13.2(m+1)p*m

14.1p*m*m

T = 2(m+1)(m+1) + m*m + T1(m) + T2(m) + 2(p+1) + 4p(m+1)(m+1) + 2 p*m*n + p*m

Problema nr 16.OperatieCostNr. repetari

1.2(m+1)1

2.2nm

3.2(n+1-j)m*(m-1)

4.1m*n*(n-1)

5.1T1(n)

6.1T1(n)

7.1T1(n)

T = 2(m+1) + 2n*m +2m(n+1-j)(m-1) + m*n*(n-1) + 3T1(n)Problema nr 17.

OperatieCostNr. repetari

1.11

2.2(m+1)1

3.1m

4.1m

5.2nm

6.1m*(n-1)

7.1T2(n)

8.1m

9.1T1(n)

10.1T1(n)

T = 1 + 2(m+1) + 3m + 2n*m + m*(n-1) + 2T1(n) + T2(n)

Problema nr 18.OperatieCostNr. repetari

1.11

2.2(m+1)1

3.1m

4.2(n-1)m

5.1m*(n-1)

6.1T1(n)

7.1m

8.1T2(n)

9.1T2(n)

T = 1 + 2(m+1) + 3m + 2T2(n) + 2n*m + m*(n-1) + T1(n)

Problema nr 19.OperatieCostNr. Repetari

1.11

2.2(n+1) 1

3.1n

4.2(m+1)n

5.1m*n

6.11

7.11

8.2(n+1)1

9.1n

10.1T1(n)

11.1T1(n)

12.1T1(n)

13.1n

14.1T2(n)

15.1T2(n)

T = 3 +4(n+1) + 3T1(n) + 2T2(n) + 3n +2n(m+1) + m*n

Problema nr 20.OperatieCostNr. repetari

1.2(n+1)1

2.1n

3.1n

4.2(m+1)n

5.1n*m

6.1T1(n)

7.1T1(n)

8.1n

T = 2(n+1) + 3n + 2(m+1) + n*m + 2T1(n)