Questões de Concurso Comentadas sobre complexidade de algoritmos em algoritmos e estrutura de dados

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: 

Considere o pseudocódigo abaixo, que define uma função que recebe dois arrays, A1, A2, cada um com N elementos indexados a partir de 1, e retorna o número de elementos do array A1 que não aparecem em A2. function xpto(A1, A2, N)      contagem=0      for i=1 to N             flag=0             for j=1 to N                  if A1[i] == A2[j] then flag=1                  if flag == 0 then contagem=contagem + 1         return contagem Exatamente como foi codificado, o algoritmo da função xpto tem complexidade

O gerente de uma agência bancária recebe, diariamente, solicitações de seus clientes com dúvidas sobre a melhor decisão para aplicações financeiras e as armazena, com um código numérico crescente, num vetor de solicitações, para respondê-las ao final do expediente. Para manter o conceito de bom atendimento, o gerente gostaria, sempre que possível, que a ordem das respostas seguisse, estritamente, a ordem de chegada das solicitações. Entretanto, há casos em que é necessário, por motivos de emergência ou por prioridade legal, localizar determinado código numérico para atender à solicitação correspondente antes das demais, “furando” a fila de espera. O gerente solicitou, então, à equipe de TI do banco, uma proposta que conciliasse essas duas necessidades. Ao estudar o problema, a equipe de TI concluiu que uma solução que mapearia diretamente essa necessidade da gerência seria permitir a realização de uma busca binária sobre o vetor de solicitações ordenado pelos seus códigos numéricos.
Verificando a viabilidade dessa sugestão, o grupo de TI calculou que, se considerar a existência de N solicitações, a quantidade de iterações necessárias para localizar determinado código numérico no vetor de solitações, utilizando a busca binária, no pior caso, é

Assinale a alternativa que apresenta o tempo de execução do pior caso e do melhor caso para o algoritmo quicksort ou ordenação rápida.

Um algoritmo que apresenta a menor complexidade dentre todos os possíveis algoritmos para resolver o mesmo problema é considerado um algoritmo

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á:

O famoso algoritmo de Dijkstra soluciona um problema de grafos direcionados e não direcionados com uma certa complexidade. Qual é esse problema e qual é essa complexidade?

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(n² ).

Assinale a opção CORRETA:

Considere, por hipótese, que uma Analista de Sistemas da Câmara Legislativa está participando de um processo de avaliaçãode quatro softwares concorrentes para suporte a algumas atividades da Câmara. A Analista solicitou que cada empresafornecesse a função de complexidade do principal algoritmo do software. As funções de complexidade estão listadas abaixo.
I. f(n) = n²  II.f(n) = nlog₂n III. f(n) = 2n IV. f(n) = 3log₂n
Ao fazer a análise dos algoritmos, a Analista conclui corretamente que 

Função de complexidade de algoritmos, cujo tempo de execução ocorre tipicamente em algoritmos que resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e, depois, ajuntando as soluções:

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?

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.

Pesquisa Binária e Hash Code são duas técnicas de busca de dados em um arquivo ou tabela muito usados em informática, com grande vantagem sobre a Pesquisa Sequencial. Sobre essas técnicas, assinale a afirmação INCORRETA.

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

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

Sobre uma importante classe de complexidade, a classe dos problemas NP-completos, NÃO se pode afirmar que

A função da Memoização na estratégia Top-Down para a solução de problemas, utilizando Programação Dinâmica, é implementar um algoritmo

Utilize o método mestre para resolver recorrências das equações abaixo.

T₁ (n) = 9T₁ (n/3) + n

T₂ (n) = T₂ (2n/3) + 1

As ordens de complexidade correspondentes são

A estrutura de dados de árvore binária é amplamente utilizada na computação, podendo muitas de suas propriedades serem deduzidas na medida de sua necessidade. Ao deduzir a fórmula matemática para a profundidade de uma árvore binária completa de n folhas, constata-se que a alternativa expressando corretamente essa fórmula é