Question

ME AJUDEM POR FAVOR - CONTAGEM E EFICIÊNCIA DER ALGORITMO - 45 PONTOS!!

1) Para os trechos de código mostrados, quantas vezes a instrução
q = q + 1 será executada e por que?
int q = 0;
for (i = 0; i < n; i++) {
for (j = 1; j < n; j++) {
for (k = 0; k < n; k++) {
q = q + 1;
}
}
}

2) Dentre as funções x, x², log2(x) e n*log2(x), qual algoritmo apresentará o pior comportamento em velocidade?

Answer 1

1) Para os trechos de código mostrados, quantas vezes a instrução
q = q + 1 será executada e por que?
int q = 0;
for (i = 0; i < n; i++) {
   for (j = 1; j < n; j++) {
      for (k = 0; k < n; k++) {
         q = q + 1;
      }
   }
}

o loop mais externo vai variar o i de 0 a n-1, portanto n vezes

O loop mais interno vai variar o k de 0 a n-1, do mesmo jeito, n vezes

O loop do meio vai variar o j de 1 a n-1, ou seja, n-1 vezes

Portanto, o comando q = q + 1 ;  
(que poderia ser substituido por q++)
vai ser executado n²*(n-1) vezes

2) o maior esforço computacional é n*log2(x). Além de fazer a multiplicação vai fazer o logarítimo natural de x. É o mais lento de todos.