questionei.comQuestões
Explore as questões disponíveis e prepare-se para seus estudos!
Ano: 2021Banca: FGVOrganização: TJ-RODisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
João precisa codificar uma função f(A), onde A é um array
unidimensional de números inteiros, que deve retornar o maior
valor armazenado em A.
A complexidade de um algoritmo eficiente para a função f, para
um array com n (n ≥ 1) elementos, deveria ser:
Ano: 2024Banca: IBFCOrganização: IMBELDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
O algoritmo MERGE SORT emprega a técnica “divisão e conquista” para ordenar uma lista de valores. A ordem de complexidade deste algoritmo, no pior caso, é:
Ano: 2017Banca: IFBOrganização: IFBDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Leia as afirmativas a seguir a respeito das principais classes de comportamento assintótico.
I) A complexidade logarítmica é típica de algoritmos que resolvem problemas, transformando-os
em problemas menores e depois agrupando as soluções dos problemas menores.
II) A complexidade quadrática é típica de algoritmos onde os dados são processados ao pares
muitas vezes com um anel dentro de outro.
III) Um algoritmo com complexidade exponencial é mais rápido que um algoritmo linear.
IV) Um algoritmo com complexidade n! (n fatorial) apresenta um comportamento pior que um
algoritmo com complexidade 2n
.
V) A complexidade do algoritmo de pesquisa binária é logarítmica.
Assinale a alternativa que apresenta somente as afirmativas CORRETAS.
Ano: 2017Banca: IFBOrganização: IFBDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Considere a função de complexidade f(n) = 3n3
+ 4n2
+2n. Selecione a opção abaixo contendo
o menor valor para a constante c, c>0, para que g(n) = c.n3
domine assintoticamente f(n), para
n>= 1.
Ano: 2017Banca: IFBOrganização: IFBDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Leia as afirmativas a seguir considerando que f(n) e g(n) são funções positivas.
I) Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de
complexidade g(n).
II) Se g(n) é O(f(n)), f(n) é um limite superior para g(n).
III) Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)).
IV) Se g(n) = n2
e f(n) = (n+1)2
temos que g(n) é O(f(n)) e f(n) é O(g(n)).
V) Se g(n) = 2n+1 e f(n) = 2n
temos que g(n) = O(f(n)).
Assinale a alternativa que apresenta somente as afirmativas CORRETAS.
Ano: 2014Banca: FUMARCOrganização: AL-MGDisciplina: Estruturas de Dados e AlgoritmosTemas: Análise de Complexidade | Estruturas de Pilhas | Estruturas de Dados | Teoria dos Algoritmos
Analise as seguintes afirmativas sobre a análise de complexidade das operações possíveis em estruturas de dados do tipo Pilha:
I. A operação de inserção de um elemento na pilha precisa reorganizar a estrutura de dados, podendo gastar um tempo de execução de O(n).
II. A operação de retirada de um elemento da pilha é uma operação de tempo constante O(1).
III. Na operação de consultar toda a pilha, todos os elementos são percorridos, gastando-se um tempo de execução de O(n).
Estão CORRETAS as afirmativas:
I. A operação de inserção de um elemento na pilha precisa reorganizar a estrutura de dados, podendo gastar um tempo de execução de O(n).
II. A operação de retirada de um elemento da pilha é uma operação de tempo constante O(1).
III. Na operação de consultar toda a pilha, todos os elementos são percorridos, gastando-se um tempo de execução de O(n).
Estão CORRETAS as afirmativas:
Ano: 2012Banca: UPENET/IAUPEOrganização: JUCEPEDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Sobre a complexidade de algoritmos, analise os itens abaixo:
I. Se o número de passos realizados por um algoritmo A é (n2 + n) para várias entradas de tamanho n, então a complexidade de A é O(n2 ).
II. Se a complexidade de pior caso de um algoritmo A for n, então o número de passos efetuados por A é O(n), qualquer que seja a entrada.
III. Se a complexidade de pior caso de um algoritmo A for n, então podemos afirmar que A é O(n) e também O(n2 ), mas a afirmação O(n) é mais precisa e deve ser utilizada.
Assinale a alternativa CORRETA.
I. Se o número de passos realizados por um algoritmo A é (n2 + n) para várias entradas de tamanho n, então a complexidade de A é O(n2 ).
II. Se a complexidade de pior caso de um algoritmo A for n, então o número de passos efetuados por A é O(n), qualquer que seja a entrada.
III. Se a complexidade de pior caso de um algoritmo A for n, então podemos afirmar que A é O(n) e também O(n2 ), mas a afirmação O(n) é mais precisa e deve ser utilizada.
Assinale a alternativa CORRETA.
Ano: 2018Banca: IADESOrganização: CFMDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Quando dois elementos estão fora de ordem, há uma inversão, e esses dois elementos são trocados de posição, ficando em ordem correta. Assim, o primeiro elemento é comparado com o segundo. Se uma inversão for encontrada, a troca é feita. Em seguida, independentemente de se houve ou não troca após a primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma inversão seja encontrada, a troca é feita. O processo continua até que o penúltimo elemento seja comparado com o último. Com esse processo, garante-se que o elemento de maior valor do vetor seja levado para a última posição. A ordenação continua com o posicionamento do segundo maior elemento, do terceiro etc., até que todo o vetor esteja ordenado.
CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução a Estruturas de Dados. Rio de Janeiro: Elsevier, 2004, com adaptações.
Em relação ao algoritmo descrito, é correto afirmar que a
respectiva ordem de complexidade, no pior caso, é
Ano: 2024Banca: IF-MGOrganização: IF-MGDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Análise de Complexidade
Um pesquisador está usando um algoritmo genético para encontrar o melhor conjunto de features possíveis para um problema. No entanto, durante a execução do algoritmo o pesquisador percebe que as soluções geradas sempre divergem para a mesma solução subótima.
Tendo em vista o cenário apresentado, assinale a alternativa que apresenta a ação que irá melhorar a exploração do espaço de respostas a fim de evitar a rápida convergência.
Ano: 2024Banca: FGVOrganização: CVMDisciplina: Estruturas de Dados e AlgoritmosTemas: Análise de Complexidade | Teoria dos Algoritmos
O cálculo da complexidade computacional é essencial para
verificar a viabilidade do algoritmo. Observe o código a seguir,
em Python, para o problema da torre de Hanoi.
def hanoi(n, o, d, a):
if n==1:
print("D1 de "+o+" p/ "+d)
else:
hanoi(n-1, o, a, d)
print("D"+str(n)+" de "+o+" p/ "+d)
hanoi(n-1, a, d, o)
A complexidade desse algoritmo no pior caso é:
..