Para cada um dos algoritmos abaixo:
Algoritmo 1 Algoritmo 2
  1. Calcule o número de operações de:
    a. Declaração de Variáveis
    b. Atribuições
  2. Calcule o número de operações em função de & int count =0 ; & int i ; & for (i=0 ; i para cada um dos algoritmos:
    a. Comparação menor que
    b. Comparação igual a
    c. Incremento no melhor caso
    d. Incremento no pior caso

Passo 1

Beleza, o enunciado pede pra gente analisar dois trechos de código e “contar” quantas vezes cada tipo de operação acontece. O conteúdo aqui é análise de algoritmo (contagem de operações básicas: declarações, atribuições, comparações e incrementos). Vamos precisar lembrar como funciona um laço for (quantas vezes testa a condição, executa o corpo e faz o incremento) e como cada operador (=, ++, <, ==, *=) conta como uma operação.

Passo 2

Algoritmo 1:
int count = 0;
int i;
for(i = 0; i < n; i++)
    if (i % 2 == 1)
        count++;
• Declarações de variáveis: contamos cada int nome; como 1 operação de declaração. Aqui temos
  1. int count
  2. int i
    → total = 2 declarações.
    • Atribuições: todo uso de = (fora de comparações) é atribuição. Aqui são
  3. count = 0;
  4. i = 0; (inicialização do for)
    → total = 2 atribuições.

Passo 3

Algoritmo 2:
for (int i = 1; i <= n; i *= 2)
    if (i % 2 == 0)
        printf("Olá");
• Declarações de variáveis: dentro do for declaramos int i → 1 declaração.
• Atribuições: usamos = só em i = 1; na inicialização → 1 atribuição.

Passo 4

Agora vamos contar, em função de n, quantas vezes ocorrem comparações e incrementos no Algoritmo 1.
a) Comparação menor que (i < n):
O for testa i < n a cada iteração e uma vez extra pra sair. Se i vai de 0 até n-1, são
n + 1
testes <.
b) Comparação igual (i % 2 == 1):
O if roda uma vez a cada iteração, ou seja, exatamente
n
testes ==.
c) Incremento no melhor caso:
Aqui o incremento do laço é i++, que acontece a cada iteração (sem variação). São
n
execuções de i++ (melhor e pior caso são iguais).
d) Incremento no pior caso:
Como não muda, continua
n

Passo 5

Para o Algoritmo 2:
a) Comparação menor ou igual (i <= n):
Começamos em i=1 e dobramos até ultrapassar n. O número de iterações é
1,2,4,8,dots,2^k <= n < 2^k+1
logo k = lfloor log2 nrfloor. O teste i <= n acontece uma vez a mais pra sair do laço:
lfloor log2 nrfloor + 1
b) Comparação igual (i % 2 == 0):
Roda dentro do for em cada iteração, ou seja, também
lfloor log2 nrfloor + 1
testes ==.
c) Incremento no melhor caso:
O “incremento” aqui é i *= 2, que roda uma vez por iteração (sem variação), então
lfloor log2 nrfloor + 1
d) Incremento no pior caso:
Igual ao acima, continua
lfloor log2 nrfloor + 1

Resposta

Algoritmo 1:
1.a) Declarações = 2
1.b) Atribuições = 2
2.a) < = n + 1
2.b) == = n
2.c) incremento (i++) melhor caso = n
2.d) incremento (i++) pior caso = n
Algoritmo 2:
1.a) Declarações = 1
1.b) Atribuições = 1
2.a) <= = lfloor log2nrfloor + 1
2.b) == = lfloor log2nrfloor + 1
2.c) atualização (i *= 2) melhor caso = lfloor log2nrfloor + 1
2.d) atualização (i *= 2) pior caso = lfloor log2nrfloor + 1

Exercícios relacionados