Para cada um dos algoritmos abaixo:
Algoritmo 1 | Algoritmo 2 |
---|---|
- Calcule o número de operações de:
a. Declaração de Variáveis
b. Atribuições - Calcule o número de operações em função de
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 temosint count
int i
→ total = 2 declarações.
• Atribuições: todo uso de=
(fora de comparações) é atribuição. Aqui sãocount = 0;
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
• Atribuições: usamos
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
, quantas vezes ocorrem comparações e incrementos no Algoritmo 1.
a) Comparação menor que (
O , são
i < n
):O
for
testa i < n
a cada iteração e uma vez extra pra sair. Se i
vai de 0 até
testes
<
.b) Comparação igual (
O
i % 2 == 1
):O
if
roda uma vez a cada iteração, ou seja, exatamentetestes
==
.c) Incremento no melhor caso:
Aqui o incremento do laço é
Aqui o incremento do laço é
i++
, que acontece a cada iteração (sem variação). Sãoexecuções de
i++
(melhor e pior caso são iguais).d) Incremento no pior caso:
Como não muda, continua
Como não muda, continua
Passo 5
Para o Algoritmo 2:
a) Comparação menor ou igual (
Começamos em e dobramos até ultrapassar
. O número de iterações é
i <= n
):Começamos em
logo
. O teste
i <= n
acontece uma vez a mais pra sair do laço:b) Comparação igual (
Roda dentro do
i % 2 == 0
):Roda dentro do
for
em cada iteração, ou seja, tambémtestes
==
.c) Incremento no melhor caso:
O “incremento” aqui é
O “incremento” aqui é
i *= 2
, que roda uma vez por iteração (sem variação), entãod) Incremento no pior caso:
Igual ao acima, continua
Igual ao acima, continua
Resposta
Algoritmo 1:
1.a) Declarações = 2
1.b) Atribuições = 2
2.a)
2.b)
2.c) incremento (
2.d) incremento (
1.a) Declarações = 2
1.b) Atribuições = 2
2.a)
<
=
2.b)
==
=
2.c) incremento (
i++
) melhor caso =
2.d) incremento (
i++
) pior caso =
Algoritmo 2:
1.a) Declarações = 1
1.b) Atribuições = 1
2.a)
2.b)
2.c) atualização (
2.d) atualização (
1.a) Declarações = 1
1.b) Atribuições = 1
2.a)
<=
=
2.b)
==
=
2.c) atualização (
i *= 2
) melhor caso =
2.d) atualização (
i *= 2
) pior caso =