A respeito de funções e algoritmos, assinale a afirmativa correta.
Se a complexidade de tempo de um algoritmo é da ordem de Θ (n log n), é correto afirmar que esse algoritmo também é
A respeito de funções e algoritmos, assinale a afirmativa correta.
Seja T um texto e C, uma cadeia de caracteres, onde n e m correspondem ao tamanho de T e C, respectivamente. Sobre a busca de C em T, é correto afirmar que o algoritmo de:
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
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?
Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em uma árvore de busca binária. Após a completa inserção de todos os elementos nesta árvore, são feitas buscas de números na mesma. O tempo médio de busca de um número nesta árvore é
Um programador decidiu utilizar, em determinado sistema de análise estatística, uma árvore AVL como estrutura de dados. Considerando-se n a quantidade de elementos dessa árvore, o melhor algoritmo de pesquisa, com base em comparações, possui complexidade de tempo, no pior caso, igual a
Considere um arquivo não ordenado, organizado sequencialmente e contendo N registros.O número médio de acessos que precisa ser feito para localizar um registro nesse arquivo, numacesso sequencial é:
tempo de execução do pior caso do algoritmo de ordenação Quicksort é:
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,
Considere os seguintes algoritmos e suas complexidades na notação Big O:
- Algoritmo A: O(log n)
- Algoritmo B: O(n2)
- Algoritmo C: O(n . log n)
Considerando-se o pior caso de execução destes algo- ritmos, é correto afirmar que o algoritmo
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?
São algoritmos de ordenação, cuja complexidade é O(n log n), EXCETO:
Sabe-se que o valor de um dado armazenado com um tipo inteiro é o próprio número inteiro na base binária que
forma uma cadeia de bits. A largura (ou precisão) de um tipo inteiro é a quantidade de bits disponíveis para a sua
representação. O algoritmo abaixo avalia a quantidade de bits necessária para armazenar um inteiro. Determine
sua complexidade.
int numero_bits (int x) {
int bits = 0;
while (x != 0) { bits++; x=x/2; }
return bits;
}
Busca ou pesquisa binária é um algoritmo de busca em vetores ordenados. Sobre o algoritmo de busca binária é correto afirmar:
I - No pior caso tem complexidade O(log n).
II - No melhor caso tem complexidade O(log n).
III - No caso médio tem complexidade O(1).
IV - No melhor caso tem complexidade O(n).
Está(ão) correta(s)
Métodos de classificação por contagem são mais eficientes em termos de complexidade de tempo de execução que os métodos de classificação por comparação de chave.
Considerando que A seja um algoritmo, {E1, ..., Em} o conjunto de todas as entradas possíveis de A, e ti o número de passos efetuados por A quando a entrada for Ei , assinale a opção correta.
Se f é uma função de complexidade para um algoritmo F, então O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a opção que apresenta somente algoritmos que possuem complexidade assintótica quando f(n) = O(n log n).
Considerando o conceito de Complexidade de Algoritmos, representado por O(função), assinale a alternativa que apresenta, de forma crescente, as complexidades de algoritmos.
Analise as afirmativas:
I. Considere o método de ordenação que implementa o seguinte processo: uma coleção desordenada de n elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva da subrotina. Os resultados das duas reaplicações são, então, combinados pela intercalação dos elementos de ambas, resultando em uma coleção ordenada. A complexidade do caso médio desse algoritmo é expressa por O(n log2 n).
II. Existem aplicações para listas lineares nas quais inserções, retiradas e acessos a itens ocorrem sempre em um dos extremos da lista. Nestes casos a estrutura adequada para resolvê-los é a pilha ou stack.
III. No método Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.
Está correto o que se afirma em
Em uma reunião de análise de desempenho de um sistema WEB, um programador apontou corretamente que a complexidade de tempo do algoritmo bubblesort, no pior caso, é
Todos os N nomes de uma lista de assinantes de uma companhia telefônica foram inseridos, em ordem alfabética, em três estruturas de dados: uma árvore binária de busca, uma árvore AVL e uma árvore B.
As alturas resultantes das três árvores são, respectivamente,
Sabendo que o algoritmo pode ser considerado como uma sequência de ações executáveis para obtenção de uma solução para um determinado tipo de problema e que pode ser mensurado para se obter um tempo de execução em relação a algumas variáveis, marque os 3 cenários apresentados pelo tempo de execução de um algoritmo.
A complexidade de execução do algoritmo heapsort, no pior caso é:
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:
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:
Um sistema de controle distribui os processos para os juízes de um tribunal utilizando critérios de prioridade associados a cada processo, de modo que novos processos podem ser analisados pelos juízes enquanto outros aguardam análise.
Considerando essas informações, julgue os itens a seguir, acerca dos tipos básicos de estruturas de dados e de operações sobre estruturas de dados.
Caso a implementação seja realizada por meio de max-heap, a operação de remoção de processos de maior prioridade levará um tempo de ordem O(log n).
Um vetor ordenado de inteiros com 2N+1 elementos, com N=0, será usado para criar uma árvore binária de busca da seguinte maneira: o elemento central, de índice N, será usado para criar a raiz; depois, serão inseridos na árvore todos os elementos na seguinte ordem de índices: N-1, N+1, N-2, N+2, ..., 1, 2N-1, 0, 2N.
Assumindo que a altura de uma folha é zero, qual será a altura resultante dessa árvore?
Um programador recebeu a tarefa de elaborar um algoritmo para criar uma única lista encadeada, não necessariamente ordenada, a partir de duas listas encadeadas ordenadas já existentes.
Cada uma das listas originais possui ponteiros para o primeiro e para o último elementos. Qual é a complexidade do algoritmo mais eficiente que esse programador pode produzir?
Considere o seguinte pseudocódigo, no qual uma rotina com complexidade O(n) é aplicada em um laço duplo.
No que diz respeito à engenharia de testes, julgue o item subsecutivo.
No que concerne a complexidade e eficiência de algoritmos, é correto afirmar que
Sobre a análise de algoritmos, é CORRETO afirmar que
Os números 1,2,3,...,N foram inseridos de forma ordenada em uma árvore binária de busca, em uma árvore AVL e em um vetor para o qual foi decidido que a posição do número i seria dada pelo índice i-1. Depois, sabendo-se que nenhuma inserção posterior será realizada em nenhuma das três estruturas, decidiu-se fazer uma busca em cada uma destas. Os tempos que se podem obter para essa busca na árvore binária de busca, na árvore AVL e no vetor são, respectivamente,
O algoritmo de ordenação de pior complexidade temporal no caso médio, dentre os que se seguem, é
A pesquisa de dados envolve a determinação da chave pesquisada estar ou não entre os dados pesquisados e, caso esteja, que seja encontrada sua localização. Em computação, a pesquisa tem um papel importante, pois de posse do campo chave a ser pesquisado fica mais fácil encontrar determinado arquivo, ou mesmo qualquer item que se queira buscar. Já a classificação envolve a organização dos dados em uma determinada ordem, por exemplo: crescente, decrescente, ordem alfabética, numérica, entre outros. Acerca dos algoritmos de pesquisa e classificação, analise as afirmativas a seguir.
I. Diz-se que o algoritmo 0(log n) tem um tempo de execução linear.
II. A pesquisa binária executa em 0(log n) vezes, pois cada passo remove metade dos elementos restantes.
III. O algoritmo de classificação por inserção executa no tempo 0(n²), no pior caso e no caso médio.
IV.No pior caso, a primeira chamada à classificação por intercalação tem de fazer 0(n) comparações para preencher os n slots no array final.
Estão corretas apenas as afirmativas
Considere o seguinte pseudocódigo, no qual uma rotina com complexidade O(n) é aplicada em um laço duplo.
PARA i ←1 ATÉ n FAÇA
INÍCIO
PARA j ←1 ATÉ i FAÇA
INÍCIO
rotina com complexidade O(n);
FIM;
FIM PARA;
FIM;
FIM PARA;
Em seu pior caso, o tempo de ordenação do algoritmo Quicksort sobre um arranjo de n números é igual a
A análise de complexidade de algoritmos é importante para o projeto de algoritmos eficientes desde sua concepção. Assinale a alternativa CORRETA.
Um algoritmo de complexidade exponencial pode ser representado por qual notação?
A preocupação com a complexidade de algoritmos é de extrema importância para o projeto de algoritmos eficientes. Neste contexto, a complexidade de tempo no pior caso para o algoritmo de ordenação QuickSort é
O algoritmo a seguir apresenta uma operação com pilhas.
ocupar (pt);
pt —> info := novo_valor;
pt —> prox := topo;
topo := pt;
Sobre o algoritmo acima é correto afirmar que se refere ao
Para projetar algoritmos eficientes um desenvolvedor deve estar preocupado com a complexidade deste algoritmo, desde sua concepção.
Considere a seguinte função T(n) que mede os recursos (ex. tempo de execução) que um algoritmo necessita no pior caso para processar uma entrada qualquer de tamanho n:
T(n) = O(log(n))
Sabendo que O(log(n)) é a ordem da complexidade de tempo do
algoritmo seguindo a notação "big O", é correto afirmar que este
algoritmo tem complexidade de ordem:
Considere o algoritmo abaixo.
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 2) + fibonacci(n - 1);
}
A complexidade deste algoritmo, na notação Big O, é
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, é
Uma árvore binária completa de busca, isto é, uma árvore em que todos os níveis têm o máximo número de elementos, tem um total de N nós.
O número máximo de comparações necessárias para encontrar um elemento nessa árvore é
Analise as afirmativas a seguir sobre complexidade de algoritmos:
I. Algoritmos de complexidade O(n log n) resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e depois ajuntando as soluções.
II. Algoritmos de complexidade O(1) são chamados de complexidade linear, onde um pequeno trabalho é realizado sobre cada elemento de entrada.
III. Algoritmos de complexidade O(n) são chamados de complexidade constante, onde o tempo de execução cresce na mesma proporção do crescimento da estrutura de dados.
Estão CORRETAS as afirmativas:
Analise as afirmativas a seguir sobre complexidade de algoritmos:
I. Algoritmos de complexidade O(log n) são chamados de complexidade logarítmica e resolvem um problema quebrando-o em problemas menores.
II. Algoritmos de complexidade O(n) são chamados de complexidade linear, em que um pequeno trabalho é realizado sobre cada elemento de entrada.
III. Algoritmos de complexidade O(1) são chamados de complexidade constante, em que as instruções do algoritmo são executadas um número fixo de vezes.
Estão CORRETAS as afirmativas:
Uma das medidas de qualidade do código de um software é a Complexidade, que pode ser medida por meio da complexidade ciclomática.
Considere um grafo de fluxo que possui 5 nós e 12 arcos.
Qual a complexidade ciclomática desse grafo?
Utilize o método mestre para resolver recorrências das equações abaixo.
T1 (n) = 9T1 (n/3) + n
T2 (n) = T2 (2n/3) + 1
As ordens de complexidade correspondentes são
Uma transformação polinomial é uma ferramenta fundamental na demonstração de que determinado problema é NP-difícil.
Avalie as afirmações sobre propriedades que transformações polinomiais devem satisfazer.
I. Para toda transformação polinomial, deve existir uma Máquina de Turing determinística que a computa em tempo polinomial.
II. Se uma transformação polinomial transforma um elemento de linguagem A em um elemento de linguagem B, então A é um subconjunto não necessariamente próprio de B.
III. Se uma transformação polinomial transforma um elemento de uma linguagem A em um elemento de linguagem B, e A pertence a NP, então B pertence a NP.
IV. A quantidade de espaço utilizada pela transformação pode ser limitada por uma constante.
Está correto apenas o que se afirma em
Avalie as afirmações abaixo:
I. A classe P e a classe NP são disjuntas.
II. A classe P é um subconjunto da classe co-NP.
III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.
IV. A interseção das classes NP e co-NP é vazia.
Está correto apenas o que se afirma em
Considere as seguintes afirmações sobre algoritmos e estruturas de dados:
I. Filas são estruturas do tipo FIFO (First In First Out).
II. A inserção no fim de uma lista duplamente encadeada e não ordenada é realizada em O(n).
O tempo de execução do algoritmo quicksort no pior caso é O(n2 ).
Assinale a opção CORRETA:
A notação “O” que determina ordem de complexidade e eficiência de um algoritmo pode ser formalizada como se segue:
T(n) = O (ƒ(n))
Se existirem inteiro m e constante c tais que
T(n) ≤ cƒ(n) para n > m.
Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes algoritmos. Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém utilizando algoritmos diferentes.
Considere as seguintes ordens de complexidade no tempo:
T1(n) = n, T2(n) = nlogn, T3(n) = n² , T4(n) = 2n
Um método de busca bastante utilizado, conhecido como hash, baseia-se na utilização que mapeia chaves em endereços de memória, de modo que os dados associados a cada chave possam ser rapidamente localizados e lidos. Quando há conflitos de localização, algum algoritmo de separação é adotado.
Considere uma tabela hash armazenada em um arquivo no disco rígido. Supondo-se que a mesma possua uma função de hash razoavelmente protegida de conflitos, o número médio de acessos ao disco, necessários para localizar uma chave em um universo de N chaves, é mais próximo de
Referente à análise da complexidade de algoritmos, preencha as lacunas e assinale a alternativa correta.
Um ___________ é, em outras palavras, uma norma executável para estabelecer um determinado efeito desejado, que na prática será geralmente a obtenção de uma solução a certo tipo de problema. O conceito central da ______________ e da ciência da computação é o de algoritmo.
A seguir são apresentados alguns resultados do cálculo da complexidade média de alguns algoritmos conhecidos para ordenação de vetores.
Qual entre eles apresenta um bom fator de complexidade em sua execução e deve ser utilizado?
Um algoritmo de complexidade nlogn é mais complexo que um algoritmo de complexidade n2 .
Os algoritmos de ordenação são utilizados para os mais diversos cenários de dados. Apesar de terem o mesmo objetivo (ordenação), possuem diferentes complexidades em relação ao número (n) de elementos a serem ordenados. O “quiksort” se destaca como um dos algoritmos mais rápidos para ordenação. No pior caso, a complexidade “quicksort” será:
Analise os dois algoritmos a seguir:
Algoritmo1: Algoritmo2:
função algo(n) função algo(n)
se n < 2 então i <- 1
retorne n j <- 0
caso contrário para k de 1 até n faça
retorne algo(n - 1) + algo(n - 2) x <- i + j
i <- j
j <- x
retorne j
Em relação aos algoritmos expostos, é correto afirmar que
É correto afirmar que a complexidade assintótica de algoritmos é usada
Considere o código-fonte que segue:
int f1(int n) {
if (n == 0 II n == 1) return n;
else return (2 * f1(n-1) + 3 * f1(n-2)); }
int f2(int n) {
int a; int[] X = new int [n];
int[] X = new int [n]; int[] Z = new int [n];
X [0] = Y [0] = Z [0] = 0;
X [1] = 1; Y [1] = 2; Z [1] = 3;
for (a = 2; a <= n; a ++) {
X [a] = Y [a-1] + Z [a-2];
Y [a] = 2 * X [a]; Z [a] = 3 * X [a]; }
return X [n]; }
Qual é o tempo de execução de f1(n) e f2(n),
respectivamente?
Coloque F (falso) ou V (verdadeiro) nas funções abaixo, considerando a notação de complexidade O, e assinale a seguir a opção correta.
( ) f - 9 + log n = 0(n)
( ) f= 255 = 0(1)
( ) f = 37 + 215n = 0(2n)
( ) f=25 + 218+n = 0(2n)