Algoritmos e Estruturas de Dados [LEEC] (2024/2025)

Lista de exercícios

Prática 11 (26/mai/2025)

Exercício sobre complexidade computacional.
Desenvolvimento do projeto prático.

Exercício 16: Complexidade computacional

Problema adaptado do 2º teste do ano passado.

Considere a seguinte função, que tem o nome f:

int f(int n, int x){
  int soma = 0;
  for (int i = 0 ; i < n ; i++){
    soma = soma + x;  // instrução interna do ciclo for
  }
  return soma;
}

1. Para a chamada f(1000,5), quantas vezes é executada a instrução interna do ciclo for?

2. Qual a complexidade temporal da função f (no caso pior)? [A resposta correta é uma das seguintes: O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n), O(3n), O(n!).]

3. Escreva uma função g equivalente à função f, mas que tenha uma complexidade temporal substancialmente mais baixa:

   int g(int n, int x){
   
   
   
   }
   

4. Diga qual a complexidade temporal da sua função g.

Fase 2 do projeto

No programa principal

void cmdAvancaTempo(Supermercado s, string args){
	char lixo[MAX_LINHA];
	int n;
	if (sscanf(args,"%d %s", &n, lixo) != 1
	|| n < 0)
		invalidos();
	else {
		int agora = tempoAvancaSupermercado(s, n);
		printf("Tempo corrente: %d segundos\n", agora);
	}
}

No sistema

É preciso fazer passar o tempo, um segundo de cada vez.

A programação do que acontece em cada segundo pode talvez ser feita no sistema com o argumento de que é preciso coordenar caixas, clientes e história.

Uma alternativa é programar o que acontece em cada segundo no gestor das caixas, com o argumento de que a passagem do tempo decorre nas caixas. É isso que aparece o esboço abaixo.

Mas, nesse caso, o sistema precisa de passar muitos dados para o gestor das caixas poder fazer o seu trabalho. É preciso passar, pelo menos: o tempo corrente, os clientes (para remover os clientes que saem) e a história (para adicionar um registo por cada cliente que sai).

int tempoAvancaSupermercado(Supermercado s, int n){
	for (int i = 0; i < n; i++){
		// avanca tempo
		avancaTempoCaixas(...)  // manda avancar tempo em cada caixa
	}
	// retornar o momento corrente
}