1. Considere as seguintes funções:
   
   
   1. 10.n^p
   2. log n
   3. log ( n² )
   4. 30.n³.log n
   5. 50.n.log² n
   6. (log n)^{log n}
   7. n/log n
   8. 70.n
   9. log log n
   10. 90.n².log n + n³. log n
   
   
   • Coloque as funoeacima em ordem de crescimento assintótico, i.e. valor
     quando n ¾® ¥.
     
     
   • Utilize pelo menos três vezes cada um dos símbolos O,    W,    Q,    o, e w para indicar a relação existente entre pares das funoeacima (não vale recíprocos).
   
   
2. Dê contra-exemplos para as implicações:
   1. Se f(n) = O(s(n)) e g(n) = O(t(n))
      então f(n) - g(n) = O(s(n)-t(n))
   2. Se f(n) = O(s(n)) e g(n) = O(t(n))
      então f(n) / g(n) = O(s(n)/t(n))
   
   
3. Encontre as funoeg_a(n) e g_b(n) que estimam (o mais precisamente possível) o número de operaoerealizadas pelos programas nos a e b, respectivamente.
   
   

   1. #define  MaxN        3000
      struct par
      {  int i1;
         int i2; };
      
      int   V[MaxN + 1];
      
      main()
      {
        struct par mima;
      
        scanf("%d", &n);
      
        for (i=1; i<=n; i++)
          {
            V[i] = 2*MaxN*rand();
          }
        
        Contador = 0;
        mima = minmax(1, n);
        printf("\n\n Minimo e maximo do vetor: V[%d]=%d e V[%d]=%d \n",
               mima.i1, V[mima.i1], mima.i2, V[mima.i2]);
        printf("\n Numero de comparacoes: %d \n", Contador);
      }
      
      struct par minmax( inicio, fim )
      int inicio, fim;
      {
        struct par mm, mm1, mm2;
        int meio;
      
        printf(" %d %d \n",inicio, fim);
        
        if (fim - inicio <= 1)
          {
            Contador++;
            if( V[inicio] < V[fim] )
              {
                mm.i1 = inicio;
                mm.i2 = fim;
              }
            else
              {
                mm.i1 = fim;
                mm.i2 = inicio;
              }
          }
        else
          {
            meio = ((inicio + fim)/2);
            printf("  %d \n",meio);
            
            mm1 = minmax(inicio, meio);
            mm2 = minmax(meio+1, fim);
      
            Contador++;
            if ( V[mm1.i1] > V[mm2.i1] )
              {
                mm.i1 = mm2.i1;
              }
            else
              {
                mm.i1 = mm1.i1;
              }
      
            Contador++;
            if ( V[mm1.i2] < V[mm2.i2] )
              {
                mm.i2 = mm2.i2;
              }
            else
              {
                mm.i2 = mm1.i2;
              }
          }
        
        return( mm );
      }      
      

   2. program teste;
      const MAX = suficiente;
      var A: array [1..MAX] of integer;
          n, i: integer;
      
      procedure coloca_i (i: integer)
      var j, item: integer;
          cont: boolean;
      begin
        j := 2*i;  item := A[i]; cont := true;
        while (j <= n) and cont do
          begin
            if (j < n) and (A[j] < A[j+1])
              then j:=j+1;
            if (item > A[j])
              then cont := false;
              else
                begin
                 A[j div 2] := A[j];
                 j := j*2;
                end;
          end;
        A[j div 2] := item;
      end;
      
      begin
        read(n); (* n e' uma potencia de 2 menos 1 *)
        for i:= 1 to n do
          read(A[i]); (* Le um numero inteiro qualquer *)
      
        (* Loop Principal *)  
        for i:= (n div 2) down to 1 do
          coloca_i (i);
      end.
      

   
   
4. Analise a complexidade de pior caso dos algoritmos abaixo para ordenar um conjunto de n inteiros.
   1. Ordenação por inserção (insertion sort)
   2. Ordenação por intercalação (merge sort)
   3. Ordenação por rápida (quick sort)
   4. Ordenação por radicais (radix sort), neste último considere que os inteiros são positivos e menores que 100000.
   
   
5. Dado um vetor V (ou tupla, i.e. elementos onde a ordem em que aparecem é relevante) de n elementos de Z, uma inversão ocorre quando $ i,j tais que i<j £ n e V[i] > V[j]. Diz-se que (i,j) é uma inversão de V.
   1. Escreva um algoritmo iterativo (não-recursivo) que calcule o número de inversões de V.
   2. Utilize divisão e conquista para obter um algoritmo recursivo.
   3. Escreva sua relação de recorrência.
   4. Estime um limite superior para o número de operaoedos seus algoritmos (obs.: é possível obter O(n    lg    n)).
   
   
6. Escreva um algoritmo recursivo, utilizando divisão e conquista, para multiplicar dois números binários de n bits. Escreva sua relação de recorência e obtenha mostre que O(n^log₂3) é um limite superior para o número de operaoeexecutadas pelo algoritmo. Este algoritmo deve ser baseado na idéia de multiplicação de polinômios onde observa-se que é possível obter (ax + b)(cx + d) fazendo-se apenas 3 multiplicações.

This document was translated from L^AT_EX by H^EV^EA.