Questões de Concurso Sobre complexidade de algoritmos em algoritmos e estrutura de dados

O algoritmo clássico a seguir, implementado em um método em Java, é chamado de busca binária. O algoritmo recebe como parâmetro um vetor de inteiros v e um inteiro num e retorna verdadeiro lógico caso aquele inteiro num apareça no vetor v ou falso lógico em caso contrário. Considerando que a variável n é o tamanho do vetor v, qual das opções a seguir representa a ordem de grandeza de operações que precisam ser feitas para se buscar um inteiro num com a busca binária em um vetor v de tamanho n? 

A notação O é amplamente utilizada como ferramenta de análise para calcular a complexidade computacional de um algoritmo caracterizando seu tempo de execução e limites espaciais em função de um parâmetro n.

Considere o código de um método em Java contendo o algoritmo a seguir:

Se cada um dos arranjos a e b do algoritmo tem tamanho n, então, o pior caso para o tempo de execução desse método é:

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

Utilizando a análise de complexidade de algoritmos, qual a complexidade de tempo de execução do seguinte código:

Considere o código representado na figura abaixo.

O algoritmo apresenta complexidade no pior caso de

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 é

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?

Considere a Sequência de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, ...), onde os dois primeiros termos valem 0 e 1 respectivamente, e cada termo seguinte é a soma de seus dois predecessores.
O pseudocódigo a seguir apresenta um algoritmo simples para o cálculo do N-ésimo termo dessa sequência.

Assinale a opção que mostra a complexidade desse algoritmo.