No desenvolvimento de um sistema de análise financeira, um programador uti...

No desenvolvimento de um sistema de análise financeira, um programador utilizou um algoritmo cuja complexidade de tempo, no pior caso, é igual a O(n). Outro programador aponta um algoritmo d...

Q114742 • Informática • Complexidade do algortimo • CESGRANRIO • Casa da Moeda • Analista de Nível Superior Desenvolvimento de Sistemas

No desenvolvimento de um sistema de análise financeira, um programador utilizou um algoritmo cuja complexidade de tempo, no pior caso, é igual a O(n).
Outro programador aponta um algoritmo de melhor complexidade igual a

a) O(log n).
b) O(n log n).
c) .
d) .
e) O(n!).

🚀 Desbloqueie a explicação completa

Veja comentários detalhados e resoluções exclusivas para entender o gabarito desta questão.

Marcos de Castro
31/12/1969 • 21:00

Gabarito: a)

A complexidade de tempo de um algoritmo indica o tempo que o algoritmo leva para ser executado em função do tamanho da entrada. No caso do algoritmo com complexidade O(n), isso significa que o tempo de execução do algoritmo cresce linearmente com o tamanho da entrada.

Dessa forma, se um programador aponta um algoritmo com complexidade O(log n), isso significa que o tempo de execução do algoritmo cresce de forma logarítmica com o tamanho da entrada. Portanto, o algoritmo com complexidade O(log n) é mais eficiente que o algoritmo com complexidade O(n).

Assim, a alternativa correta é a letra a) O(log n).

🔒

Conteúdo restrito

Cadastre-se para visualizar comentários e resoluções.

Criar conta grátis

Questões sobre Complexidade do algortimo

1

Q264516 • Informática • Complexidade do algortimo • FCC • TRT 19a Região • Técnico Judiciário Tecnologia da Informação
Considere os seguintes algoritmos e suas complexidades na notação Big O:

- Algoritmo A: O(log n)
- Algoritmo B: O(n²)
- Algoritmo C: O(n . log n)

Considerando-se o pior caso de execução destes algo- ritmos, é correto afirmar que o algoritmo
- a) A é o menos eficiente.
- b) C é o menos eficiente.
- c) A não é o mais eficiente nem o menos eficiente.
- d) B é o menos eficiente.
- e) C é o mais eficiente.
2

Q267286 • Informática • Complexidade do algortimo • CESGRANRIO • FINEP • Analista Desenvolvimento de Sistemas
Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?
- a) O(n²)
- b) O(1)
- c) O(n)
- d) O(n log n)
- e) O(log n)
3

Q121304 • Informática • Complexidade do algortimo • CESGRANRIO • TRANSPETRO • Analista de Sistemas Júnior
Dois vetores ordenados, contendo, cada um deles, N números inteiros, precisam ser unidos em outro vetor maior, que conterá os 2N números, que também serão armazenados de forma ordenada. A complexidade de tempo de melhor caso desse processo será, então,
- a) O(1), pois se precisa fazer apenas uma cópia simples de cada um dos elementos originais.
- b) O(log N), pois se usa a busca binária para determinar qual será o próximo elemento copiado para o vetor de destino.
- c) O(N), pois se precisa fazer uma cópia de cada um dos elementos originais, o que implica uma varredura completa de cada vetor de origem.
- d) O(Nlog N), pois se precisa fazer uma busca de cada elemento para depois inseri-lo no vetor de destino.
- e) O(N² ), pois, como há dois vetores, precisa-se fazer dois laços de forma aninhada (um dentro do outro), gerando uma multiplicação das quantidades de elementos.
4

Q118583 • Sistemas de Informação • Complexidade do algortimo • VUNESP • TJ SP • Analista de Sistemas
Considerando o conceito de Complexidade de Algoritmos, representado por O(função), assinale a alternativa que apresenta, de forma crescente, as complexidades de algoritmos.
- a) O(2ⁿ); O(n³); O(n²); O(log₂ n); O(n.log₂ n).
- b) O(n²); O(n³); O(2ⁿ); O(log₂ n); O(n.log₂ n).
- c) O(n³); O(n²); O(2ⁿ); O(n.log₂ n); O(log₂ n).
- d) O(log₂ n); O(n.log₂ n); O(n²); O(n³); O(2ⁿ).
- e) O(n.log₂ n); O(log₂ n); O(2ⁿ); O(n³); O(n²).
5

Q120591 • Informática • Complexidade do algortimo • CESGRANRIO • Petrobras • Analista de Sistemas Pleno Processos
A respeito de funções e algoritmos, assinale a afirmativa correta.
- a) O limite inferior de um algoritmo (O ) é utilizado para a análise do pior caso de sua execução.
- b) Uma função f(n) domina assintoticamente g(n), se existem duas constantes positivas c e n₀, tais que, para n =n₀, temos que |g(n)| = c|f(n)|.
- c) A função f(5log₂ N) é O²(N).
- d) A função f(5N³ + 2N²) é O(N).
- e) Se duas funções f( ) e g( ) têm limite superior justo, então f( ) é O( g( ) ) e g( ) é O( f( ) ).
6

Q119822 • Informática • Complexidade do algortimo • CESGRANRIO • Petrobras • Analista de Sistemas Júnior Processos de Negócios
Um programador precisa realizar buscas em um enorme cadastro de pessoas (tamanho igual a n) armazenado na memória principal. Para realizar um processo eficiente de busca, ele decidiu usar uma árvore AVL e obteve um tempo de execução de ordemUm colega, preocupado com a eficiência do processo de busca, sugeriu-lhe que usasse um vetor com 10 árvores AVL, onde o índice da árvore seria dado pelo último dígito do CPF de cada pessoa, dígito este que é uniformemente distribuído. Assim, cada árvore teria aproximadamente 1/10 do número de pessoas e o processo de busca poderia ser mais eficiente. Se o programador implementar a solução proposta pelo seu colega, a ordem do tempo de execução do processo de busca será
- a)
- b)
- c)
- d)
- e)
7

Q120510 • Informática • Complexidade do algortimo • FUMARC • PRODEMGE • Analista de Tecnologia da Informação
São algoritmos de ordenação, cuja complexidade é O(n log n), EXCETO:
- a) Shellsort.
- b) Quicksort.
- c) Heapsort.
- d) Radixsort.
8

Q120122 • Informática • Complexidade do algortimo • CESGRANRIO • Petrobras • Analista de Sistemas Pleno Processos
Durante a análise de um problema de programação, uma analista montou a seguinte fórmula recursiva para descrever a solução do problema:

A complexidade da solução encontrada é:
- a) O(n x log n).
- b) O(n² x log n).
- c) O(2ⁿ).
- d) O(n²).
- e) O(n³).

Mais questões de Informática →

Utilizamos cookies e tecnologias semelhantes para aprimorar sua experiência. Política de Privacidade.

Reportar erro em Conteúdo

🚀 Desbloqueie a explicação completa