A avaliação das complexidades de melhor e pior caso está vinculada aos passos executados por um algoritmo e pela operação elementar básica consider...
A avaliação das complexidades de melhor e pior caso está vinculada aos passos executados por um algoritmo e pela operação elementar básica considerada. Seja a função EncontraMaior, que retorna o maior elemento de um vetor de números não negativos: função EncontraMaior(vetor) maior = -1 para pos = 1 até n faça // n é o tamanho do vetor se maior < vetor[pos] então maior = vetor[pos] fim se fim para retorna maior fim função Assinale a alternativa que indica as complexidades de melhor e pior caso do algoritmo, considerando a operação elementar básica como a atribuição à variável maior.
A. Melhor caso: O(1); pior caso: O(n2).
B. Melhor caso: O(1); pior caso: O(1).
C. Melhor caso: O(n2); pior caso: O(n2).
D. Melhor caso: O(1); pior caso: O(n).
E. Melhor caso: O(n); pior caso: O(n2).
A. Melhor caso: O(1); pior caso: O(n2).
B. Melhor caso: O(1); pior caso: O(1).
C. Melhor caso: O(n2); pior caso: O(n2).
D. Melhor caso: O(1); pior caso: O(n).
E. Melhor caso: O(n); pior caso: O(n2).
💡 1 Resposta
Ed 
A alternativa correta é a letra D. No melhor caso, o algoritmo executa apenas uma vez a operação elementar básica, que é a atribuição à variável maior, independentemente do tamanho do vetor. Portanto, a complexidade de tempo é O(1). No pior caso, o algoritmo executa a operação elementar básica n vezes, onde n é o tamanho do vetor. Isso ocorre quando o maior elemento está na última posição do vetor ou quando todos os elementos são iguais. Portanto, a complexidade de tempo é O(n).
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
1 pág.
1 pág.
71 pág.
74 pág.
Compartilhar