A Análise de Complexibilidade

4)

a)

void proc1 (int A[n], int n) { C1 1

int i, j; C2 1

int aux; C3 1

for (j =0; j<n; j++) C4 (n+1)

for (i=0; i<n-1; i++) C5 (n+1) x (n)

if (A[i] > A[i+1]) { C6 (n+1) x (n)

aux = A[i]; C7 1

A[i] = A[i+1]; C8 1

A[i+1] = aux; C9 1

T(n) = C4(N+1) + C5(N^2+N)*C6(N^2+N)

T(n) = n + n^2 + n^2 = O(n^2) (pior caso = melhor caso)

b)

void proc2 (int n) { C1 1

int i, j; C2 1

x = 0; C3 1

for (i=1; i<=n-1; i++) C4 n

for (j=i+1; j<=n; j++) C5 n * n

for (k=1; k<=j; k++) C6 n * n * (n+1)/2

x = x+1; C7 1

T(n) = n + (n^2) + (n^3 + n^2)/2

T(n) = O(n^3)

c)

void proc3 (int n) { C1 1

int i, j, k, x; C2 1

x = 0; C3 1

for (i =1; i<=n ; i++) C4 n+1

for (j=i+1; j<=n-1; j++) C5 n+1 * n-1

for (k=1; k<=j; k++) C6 n+1 * n-1 * (n + 1)/2

x = x+1;

}

T(n) = (n+1) + 0

Tn = (n+1) + 0 = O(n+1) (pior caso = melhor caso)

5) int i, j, k, x, result = 0; C1 1

for (i = 1; i < N; i++) { C2 n

for (j = 1; j < N; j++) { C3 n*n

for (k = 0; k < M; k++) { C4 n*n*(m+1)

x = 1; C5 n*n*(m+1)

while (x < N){ C6 n*n*(m+1)

result++; C7

x += 3; C8

}

}

for (k = 1; k < 2 * M; k++) C9 n*n*(m*2)

if (k % 7 == 4) C10 n*n(m*2)

result++; C11

}

}

6) n=15;

7)

8)

a)

float func1(int