Alguém aqui entenda bem de analise de algoritmo para obter a função de custo dos algoritmos abaixo

Programação Java
#1

Observação: Considere n o tamanho do vetor vec[].

a) int soma = 0;

for(int i = 3; i < n; i++) {
soma = soma + vec[i];
}
	
System.out.println("Soma: " + soma);

b) void countSort(char arr[]){

 char output[strlen(arr)];

 int count[RANGE + 1], i;

 memset(count, 0, sizeof(count));
	 
 for (i = 0; arr[i]; ++i)
    ++count[arr[i]];
	 
 for (i = 1; i <= RANGE; ++i)
     count[i] += count[i - 1];
	 
 for (i = 0; arr[i]; ++i) {
 output[count[arr[i]] - 1] = arr[i];
 --count[arr[i]];
}
	 
for (i = 0; arr[i]; ++i)
arr[i] = output[i];

}
Análise Assintótica
#2

Pelo pouco que conheço, a análise do algoritmo será baseada na quantidade de valores recebidos x o tempo de execução. Quanto mais o tempo aumenta, dependendo dos parâmetros, pior (em termos de processamento) será o algoritmo.

#3

a)

int soma = 0;

for(int i = 3; i < n; i++) {
   soma = soma + vec[i];
}
	
System.out.println("Soma: " + soma);

Para inicializar as variáveis fora do loop vamos dizer que isso leva um tempo c:

int soma = 0
int i = 3

Agora vem as operações que estão dentro do loop. A soma do tempo delas vamos dizer que c2:

i < n;
i++;
soma = soma + vect[i];

Só que o c2 depende do loop que vai de 3 à n-1. Logo: c2 * (n - 1 - 3)

E por fim a operações abaixo do loop c3:

System.out.println("Soma: " + soma);

Logo o tempo final do algoritmo é:
T(n) = c1 + c2 * (n - 4) + c3

Em notação assintôtica, theta de N, pois para todos os casos o custo é fixo (não existe um melhor caso):
T(n) = Θ(n).

Outra maneira é contar o número de operações elementares. Mas em regra geral o tempo depende da variável N.

https://www.google.com/url?sa=t&source=web&rct=j&url=https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation&ved=2ahUKEwiw1J3-h9z0AhWLlJUCHbfzAdEQFnoECAgQAQ&usg=AOvVaw3JQrrIovJWDEDpo6X890vm

1 curtida
#4

Se vc quer uma função de custo mais detalhada, o que no frigir dos ovos não importa muito, seu professor precisa fornecer qual o custo de cada instrução que é apresentada. Se supormos que cada instrução demora uma unidade de tempo arbitrária, para simplificar a nossa vida, e tomarmos as seguintes características para embasar nossa contagem

  • ut: unidade de tempo arbitrária;
  • Declaração de variável ou declaração com atribuição de literal do tipo em questão: 1ut (ex: int i; ou int i = 0; ou double j = 5.75;);
  • Acesso a variáveis: 1ut;
  • Operadores de incremento/decremento pré ou pós-fixados: 1ut (ex: i++ ou --i);
  • Operações aritméticas, relacionais, lógicas e de atribuição: 1ut (ex: 1 + 2 ou 3 < 4 ou true && true ou x = 10 etc);
  • Operadores de atribuição compostos: 1ut (ex: i += 10 ou j -= 20 etc.)
  • Invocação de métodos: 1ut (ex: System.out.println( 20 ));
  • Retorno de método: o tempo da expressão à direita da palavra chave return;
  • Caso o código seja um método, não levar em consideração seu cabeçalho.

Precisaremos, além da contagem do tempo por instrução, calcular a quantidade de vezes que cada instrução será executada, pq é justamente dessa quantidade de vezes que conseguiremos extrair qual a “cara” da função de custo e então, com essa característica, qualificá-la em alguma classificação assintótica. Como o tamanho do problema apresentado por você vem do valor de n, temos também que pensar que n tende ao infinito, ou seja, estamos pensando em instâncias dos problemas em que a quantidade de repetições (ou recorreências) baseadas em n será MUITO grande.

Para o item a) algo como:

int soma = 0;  // 1ut (declaração com atribuição), executada uma vez


// decompondo o for:
// int i = 3;  1ut (declaração com atribuição), executada uma vez
// i < n;      3ut (dois acessos à variáveis e uma operação relacional), executada n-2 vezes. O motivo de ser n-2 é
//             fácil de se obter. Pegue um n pequeno arbitrário, por exemplo, 5. Para n = 5, vc terá i = 3, i = 4 e i = 5,
//             ou seja, em três execuções (n-2) a expressão relacional gerará verdadeiro e duas em uma falhará (esperamos
//             isso, senão teremos um loop infinito).
// i++         1ut (operador de incremento), executada n-3 vezes. i++ só executa quando se entra no bloco do for 
//             ou seja, a quantidade de vezes que a expressão relacional gerou verdadeiro
for( int i = 3; i < n; i++ ) {

    // aqui dentro temos: uma três acessos (soma, i, vec[i]), uma soma e uma atribuição, 
    // totalizando 5ut. Todo o corpo do for é executado n-3 vezes (mesmo motivo de i++,
    // que por sinal é executado após essa linha
    soma = soma + vec[i];
    
}

// aqui vem uma chamada de método mais um acesso (soma), mais uma concatenação
// totalizando 3ut que é executada apenas uma vez.
System.out.println("Soma: " + soma);

Com base nisso, podemos construir a função de custo:
T(n) = 1 + ( 1 + 3(n-2) + 1(n-3) + 5(n-3) ) + 1 =
1 + 1 + 3n -6 + n -3 + 5n -15 + 1 =
9n - 21

T(n) = 9n - 21

Agora a pergunta que se faz é, qual o termo no polinômio (essa função é polinomial)
que faz essa função crescer mais rápido? O termo é o primeiro, associado a n,
sendo assim, podemos dizer que T(n) é O(n). Em relação ao crescimento assintótico,
podemos usar algumas notações. Como normalmente estamos preocupados com o limitante
superior, usamos mais o O (ômicron), mas como o colega acima falou, nesse caso,
caberia o theta tbm. O outro item fica por sua conta.

1 curtida