Computaçao

, n1,5 , n 2 , n log( n),

n log(log( n)), n(log( n)) 2 , n log( n 2 ), 2 / n, 2 n , 2 n / 2 , 37, n 2 log( n), n 3 .
Indique quais funções têm taxa de crescimento iguais. 2. Suponha T1(n) = O(f(n)) e T2(n) = O(f(n)). Quais das seguintes afirmações são verdadeiras? a) T1(n) + T2(n) = O(f(n)) b) T1(n) - T2(n) = O(f(n)) c) T1(n) / T2(n) = O(1) d) T1(n) = O(T2(n)) 3. Vamos supor que estamos comparando implementações de ordenação por inserção e ordenação por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em 8n2 etapas, enquanto a ordenação por intercalação é executada em 64 n log n etapas. Para que valores de n a ordenação por inserção supera a ordenação por intercalação? 4. Para cada um dos seguintes trechos de algoritmos abaixo e analise o tempo estimado de execução:
...

(2) ... soma  0; Para i  0 até n-1 Faça Para j  0 até n-1 Faça soma  soma + 1; ...

(1) soma  0;
Para i  0 até n-1 Faça soma  soma + 1; ...

(3) ... soma  0; Para i  0 até n-1 Faça Para j  0 até n*n-1 Faça soma  soma + 1; ...

(4) ... soma  0; Para i  0 até n-1 Faça Para j  0 até i-1 Faça soma  soma + 1; ...

1

5. Suponha que você precisa gerar permutações aleatórias dos n primeiros números inteiros. Por exemplo, {4, 3, 1, 5, 2} e {3, 1, 4, 2, 5} são permutações corretas, mas {5, 4, 1, 2, 1} não é, porque o número 1 está duplicado e o número 3 não aparece. Esta rotina é usada com freqüência em simulações. Assumimos a existência de um gerador de números aleatórios gera_aleat(i,j), que gera inteiros entre i e j com igual probabilidade. Considere os três algoritmos: a) Preencha um vetor A de A[0] até A[n-1] como a seguir: Para preencher A[i] gere um número aleatório até encontrar um que não esteja em A[0], A[1], ..., A[i-1]. b) Igual ao algoritmo (a), mas mantendo outro vetor chamado Usados. Quando um número aleatório aleat é gerado, antes de colocá-lo no vetor A faça Usados[aleat] = 1. Isso significa que quando