Prática 2 - Análise por Operações Primitivas - Introdução à Computação 2 - 2023-2

FAC. DE FILOSOFIA, CIÊNCIAS E LETRAS DE RIBEIRÃO PRETO UNIVERSIDADE DE SÃO PAULO Introdução à Computação II - 5954006 2o semestre 2023 Prof. Renato Tinós 1 PRÁTICA 2 Análise por Operações Primitivas Seja uma função (subrotina) que, dado um vetor v com n inteiros e um inteiro x (chave de busca), retorne o índice da segunda ocorrência de x em v; caso não encontre dois valores de x no vetor v, a função deve retornar o valor -1. A busca deve ser interrompida assim que o índice da segunda ocorrência de x em v seja encontrado ou quando se chegar no último elemento do vetor. Pede-se: a) Implemente a função em C++. b) Faça a análise por operações primitivas da função. Observação: devem ser apresentadas: i) a função escrita em C++; ii) a análise por operações primitivas. FAC. DE FILOSOFIA, CIÊNCIAS E LETRAS DE RIBEIRÃO PRETO UNIVERSIDADE DE SÃO PAULO Introdução à Computação II - 5954006 2o semestre 2023 Prof. Renato Tinós PRÁTICA 2 Análise por Operações Primitivas Seja uma função (subrotina) que, dado um vetor v com n inteiros e um inteiro x (chave de busca), retorne o índice da segunda ocorrência de x em v; caso não encontre dois valores de x no vetor v, a função deve retornar o valor -1. A busca deve ser interrompida assim que o índice da segunda ocorrência de x em v seja encontrado ou quando se chegar no último elemento do vetor. Pede-se: a) Implemente a função em C++. b) Faça a análise por operações primitivas da função. Observação: devem ser apresentadas: i) a função escrita em C++; ii) a análise por operações primitivas. Respostas: int segunda_ocorrencia(int v[], int n, int x) { int cont = 0; for (int i = 0; i < n; i++) { if (v[i] == x) { cont++; if (cont == 2) { return i; } } } return -1; } A função segunda_ocorrencia recebe como parâmetros um vetor de inteiros v, o tamanho do vetor n e um valor inteiro x. A função retorna o índice da segunda ocorrência de x no vetor v, ou -1 se x não ocorrer duas vezes no vetor. A análise por operações primitivas da função é a seguinte: • Atribuição de cont = 0: 1 operação • Laço for de i = 0 até n: n+1 operações • Comparação i < n: n operações • Incremento i++: n operações • Comparação v[i] == x: n operações • Incremento cont++: no máximo n/2 operações • Comparação cont == 2: no máximo n/2 operações • Retorno return i: 1 operação • Retorno return -1: 1 operação No total, a função realiza no máximo 5n + 5 operações primitivas. Isso significa que a complexidade da função é O(n), ou seja, o tempo de execução da função cresce linearmente com o tamanho do vetor.