Grátis: Seja n o tamanho da entrada de um algoritmo para um problema P. Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de op... – Questões Respondidas

Estrutura de Dados

Outros

Seja n o tamanho da entrada de um algoritmo para um problema P. Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de operações necessárias para resolver P.
Considerando-se a análise assintótica (Big O notation), qual algoritmo possui menor complexidade?
15n + 256
2n
5 n2 + n
500 + 100 n3
100 + 10 log n

Praticando Para Aprender

há 8 meses

Praticando Para Aprender

há 8 meses

Av1 Algoritmo e complexidade

Av1 Algoritmo e complexidade

ESTÁCIO

Respostas

Ed

há 7 meses

Para determinar qual algoritmo possui a menor complexidade assintótica, vamos analisar cada uma das expressões dadas: 1. 15n + 256: A complexidade é O(n). 2. 2n: A complexidade é O(n). 3. 5n² + n: A complexidade é O(n²). 4. 500 + 100n³: A complexidade é O(n³). 5. 100 + 10 log n: A complexidade é O(log n). Agora, comparando as complexidades: - O(log n) é menor que O(n). - O(n) é menor que O(n²). - O(n²) é menor que O(n³). Portanto, o algoritmo com a menor complexidade assintótica é 100 + 10 log n, que é O(log n).

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Av1 Algoritmo e complexidade

Av1 Algoritmo e complexidade

ESTÁCIO

Mais perguntas desse material

A notação Big O é uma ferramenta importantíssima para os cientistas da computação analisarem o custo de um algoritmo. Tecnocamente falando, a notação Big O é uma notação matemática que descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou ao infinito. Ela pertence a uma família de notações inventadas por Paul Bachmann, Edmund Landau e outros, coletivamente chamadas de notação Bachmann¿Landau ou de notação assintótica. Ou seja, a notação Big O descreve a complexidade do seu código usando termos algébricos.
Diante do contexdo apresentado, podemos afirmar:
I ) Quando tentamos descobrir a Big O para uma função g(n) específica, nos preocupamos apenas com o termo dominante da função. O termo dominante é o termo que cresce mais rápido.
II ) Na notação Big O, podemos dizer que um algoritmo tem a menor complexidade quando seu custo for O(1).
III) De uma forma geral, a complexidade de um algoritmo tem relação principalmente com seu tempo de execução e espaço de memória ocupado para execução;
IV ) Na notação Big O, podemos dizer que um algoritmo que tem a complexidade O(log(n)) é mais complexo do que que custa O(n⁴);
apenas as afirmacoes I e IV são verdadeiras;
apenas as afirmações I, II e IV são verdadeiras;
apenas as afirmações II, III e IV são verdadeiras;
apenas as afirmações I, II e III são verdadeiras;
todas as afirmações são verdadeiras;

Em relação aos algoritmos de ordenação, avalie se as afirmativas a seguir são verdadeiras (V) ou falsas (F):
As afirmativas I, II e III são, respectivamente:
I. O algoritmo quick sort é muito eficiente quando há uma quantidade pequena de elementos a ordenar.
II. O algoritmo shell sort utiliza intensamente a inserção direta.
III. No algoritmo bubble sort, o número de variáveis envolvidas é pequeno.
V, F e F
V, F e V
F, F e V
F, V e V
V, V e V

Considere que os percentuais foram inseridos no vetor vet de 5 posições, a partir da posição 1, na seguinte sequência: 25.33, 27.72, 27.10, 26.90 e 27.31, ou seja, com os dados de 2008 até 2012. Um técnico em processamento de dados do TCE-RS utilizou um método para ordenar os dados de vet. O método realizou os seguintes passos no processo de ordenação:
Trata-se do método de ordenação:
Insertion sort
Fast sort
Bubble sort
Quick sort
Selection sort

O algoritmo de ordenação mais eficiente para um conjunto grande de elementos randomicamente inseridos é:
Shell sort
Quick sort
Bubble sort
Insert sort
Selection sort

Correlacione os algoritmos internos de ordenação de listas com sua descrição:
A sequência correta, de cima para baixo, é:
I. Bubble sort
II. Ordenação por seleção
III. Ordenação por inserção
IV. Shell sort
V. Quick sort
I, II, III, IV, V
V, II, III, IV, I
V, IV, II, III, I
I, III, II, IV, V
I, IV, V, III, II

Classifique cada uma das seguintes afirmacoes em "V" (se verdadeira) ou "F" (se falsa) e escolha a alternativa que corresponde à sequência correta de indicações.
I. Um registro reúne uma coleção de informações, facilitando a sua organização e o seu uso.
II. Cada informação distinta de um registro é considerada um atributo ou campo.
III. O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro.
V, F, V
V, F, F
F, V, F
F, F, V
V, V, V

Analise as seguintes afirmativas sobre os métodos de ordenação:
Assinale a alternativa correta:
I. Quick sort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e, depois, os resultados são combinados para produzir a solução de ordenação do conjunto maior.
II. Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento.
III. Shell sort é uma extensão do algoritmo de ordenação por inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita.
As afirmativas I, II e III estão erradas.
A afirmativa I está errada, e as afirmativas II e III estão certas.
As afirmativas I, II e III estão certas.
A afirmativa III está errada, e as afirmativas I e II estão certas.
A afirmativa II está errada, e as afirmativas I e III estão certas.

Sobre o conceito de Algoritmos Recursivos, analise as afirmações abaixo e, a seguir, assinale a alternativa correta.
I. Um programa tem um número limitado de procedimentos recursivos.
II. Recursividade é utilizada exclusivamente quando não se sabe solucionar um problema de maneira imediata, então é realizada a divisão em problemas menores para alcançar o resultado desejado.
III. Todos os problemas computacionais resolvidos de maneira iterativa gastam mais memória que se resolvidos de forma recursiva.
As afirmações I e II estão corretas
Somente a afirmação III está correta
Somente a afirmação II está correta
Somente a afirmação I está correta
Nenhuma das afirmações está correta

Ano: 2010 Banca: FCC Órgão: TRT - 20ª REGIÃO (SE) Prova: FCC - 2010 - TRT - 20ª REGIÃO (SE) - Técnico Judiciário - Tecnologia da Informação
Objeto que se constitui parcialmente ou é definido em termos de si próprio. Nesse contexto, um tipo especial de procedimento (algoritmo) será utilizado, algumas vezes, para a solução de alguns problemas. Esse procedimento é denominado:
Recursividade
Condicionalidade
Rotatividade
Interligação
Repetição