INF1010 3WB – L1: Complexidade..

INF1010 3WB – Lista 1: Complexidade.

Nesta lista a complexidade pedida corresponde ao O(n) - Big O - limite superior.

Exercícios

  1. Suponha que tenhamos dois algoritmos para resolver o mesmo problema. O tempo de execução de um é T1(n)=400n e o de outro T2(n)=n2. Quais são as complexidades destes algoritmos? Para que valores de n vale a pena utilizarmos o algoritmo de maior complexidade?
  2. O tempo de processamento Ti(n) de diversos algoritmos é mostrado abaixo. Qual a complexidade de cada algoritmo? Ponha os algorithms em ordem crescente de complexidade.
    • T1(n)=3nlg(n)+lg(n);
    • T2(n)=2n + n3+25;
    • T3(n,k)=n+k onde k ≤ n
    • T4(n)=T(n) = 3T(n-1)+2 para n > 1 e T(1)=O(1)
    • T5(n)=0.003log4n + log2n
    • T6(n)=100n log3n + n3 + 100n
    • T7(n)=0.01n log2n + n(log2n)2
    • T8(n)=2n + n0.5 + 0.5n1.25
    • T9(n)=0.01n + 100n2
    • T10(n)=100n + 0.01n2
    • T11(n)=n2log3n + n(log2n)3
  3. Qual a complexidade dos seguintes algoritmos: 
    1. int a = 0, b = 0;
for (i = 0; i < N; i++) {
    a = a + rand();
}
for (j = 0; j < M; j++) {
    b = b + rand();
}

      2. 


    2. 

      int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

      3. 


    3. 

      int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
    for (j = 2; j <= n; j = j * 2) {
        k = k + n / 2;
    }
}

      4. 


    4. 

      int a = 0, i = N;
while (i > 0) {
    a += i;
    i /= 2;
}

      5. 


    5.  Soma dos elementos de um vetor

      float soma (float valores[], int n)
{
	int i;
	float _soma = 0;
	for (i=0; i < n; i++)
		_soma += valores[i];
	return _soma;
}

      

      6. 


    6. Busca sequencial num vetor de tamanho n

      int buscaSequencial(char vetor[], int n, char dado)
{
	int i;
	for (i=0; i<n; i++){
		if ( vetor[i] == dado )
			return(i);
	}
	return -1;
}

      

      7. 

    7. Busca binária num vetor de tamanho n

      int buscaBinaria( char vetor[], char dado, int inicio, int fim)
{
	int meio = (inicio + fim)/2;

	if ( vetor[meio] == dado )  return (meio);

	if ( inicio >= fim ) 	return ‐1;

	if ( dado < vetor[meio] )
		return buscaBinaria (vetor, dado, inicio, meio‐1);
	else
		return buscaBinaria (vetor, dado, meio+1, fim);
}

      

      8. 


    8. multiplicação de matrizes

      void multMatriz(float **a, float **b, int n, int p, int m, float **x)
{
	int i,j,k;
	for (i=0;i<n;i++) {
		for (j=0;j<m;j++)
		{
			x[i][j]=0.0;
			for (k=0;k<p;k++)
                x[i][j]+=a[i][k]*b[k][j];
		}
	}
}

      

      9. 

    9. bublesort em um vetor de tamanho n

      void bolha (int n, int* v)
{
  int fim,i;
  for (fim=n-1; fim>0; fim--)
    for (i=0; i<fim; i++)
       if (v[i]>v[i+1]) {
          int temp = v[i] /* troca */
          v[i] = v[i+1];
          v[i+1] = temp;
       }
}

      

      10. 

    10. quicksort num vetor de tamanho n

      void rapida (int n, int* v){
   if (n > 1) {
      int x = v[0];
      int a = 1;
      int b = n-1;
      do {
         while (a < n && v[a] <= x) a++;	 /* teste a<n */
         while (v[b] > x) b--;	        /* nao testa */
         if (a < b) {          	/* faz troca */
            int temp = v[a];
            v[a] = v[b];
            v[b] = temp;
            a++; b--;
         }
      } while (a <= b);
      /* troca pivô */
      v[0] = v[b];
      v[b] = x;

      /* ordena sub-vetores restantes */
      rapida(b,v);
      rapida(n-a,&v[a]);
   }
}

      
Qual o pior caso no algoritmos de quicksort?
Mostre que ele em geral tem uma complexidade, mas no pior caso tem outra.
Como podemos evita-la?

      11. 


    11.  Solução da para o problema da Torre de Hanói

      #include <stdio.h>


void torres(int n, char origem, char destino, char auxiliar)
{
	if (n==1) {
		printf("Mova o disco 1 do Poste %c para o Poste %c\n", origem,destino);
		return;
	} else {
		torres(n-1, origem, auxiliar, destino);
		printf("Mova o disco %d do Poste %c para o Poste %c\n",n,origem,destino);
		torres(n-1, auxiliar, destino, origem);
	}
}

#define N 3
int main( void )
{
	torres(N,'A','C','B');
	return 0;
}

      

      12. 




    

    4. 


  4. A sequencia de Fibonacci é uma sequencia de números definida do seguinte modo:

             f(0) = 0
         f(1) = 1
         f(n) = f(n-1) + f(n-2) para n>1

    
Os dois algoritmos abaixo calculam o n-esimo termo da série.

    /* iterativo */
int  fibonacci_iterativo(int  n)
{
     if (n==0)  return  0;
     else if (n==1) return  1;
     else
     {
          int j,anterior=0,atual=1;
          for  (j=2;j<n;j++)
          {
                int  proximo=atual+anterior;
                anterior=atual;
                atual=proximo;
           }
           return  atual;
     }
}

/* recursivo */
int  fibonacci_rec(int  n)
{
    if  (n==0)  return  0;
    else  if  (n==1)  return  1;
    else  return  fibonacci_rec(n-1)+fibonacci_rec(n-2);
}

    
Qual a complexidade do algoritmo iterativo?
Quantas chamadas recursivas ocorrem no algoritmo recursivo faz para n=5?
Na sua avaliação qual dos dois algoritmos é mais eficiente? Por que?

    5.