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

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?

No pior caso, a complexidade do algoritmo conhecido como Busca Linear é:

O algoritmo a seguir, descrito em pseudocódigo, pode ser utilizado para ordenar um vetor A[0..n].

No pior caso, a complexidade deste algoritmo é:

Com relação à uma árvore binária de busca, assinale a alternativa correta.

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.

A complexidade do algoritmo de busca binária, sobre uma lista indexada ordenada pela chave de busca, é

Observe o código seguinte:

A complexidade média no pior caso do procedimento p, escrito em pseudocódigo, corresponde a

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:

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:

Considere o seguinte trecho de código em Java para ordenação de um conjunto de números:

A ordem de complexidade desse algoritmo, considerando que o conjunto de números (n) não está ordenado, é:

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 é

Em uma árvore AVL com grande quantidade de nós, o custo para inclusão de um nó no meio da árvore é proporcional a

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, é

Considerando o algoritmo abaixo, assinale a alternativa correta.

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, é  

O algoritmo QuickSort usa uma técnica conhecida por divisão e conquista, onde problemas complexos são reduzidos em problemas menores para se tentar chegar a uma solução. A complexidade média deste algoritmo em sua implementação padrão e a complexidade de pior caso são, respectivamente,

Considerando a área de complexidade algoritmos, assinale a opção que apresenta a classe assintótica, na notação O, com o menor tempo de resposta dada a mesma entrada de dados n.

Considere o algoritmo em pseudocódigo, descrito a seguir.

Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n²).

Um Analista, estudando a complexidade de algoritmos de busca linear (ou sequencial), concluiu corretamente que no pior caso, considerando um vetor de n elementos, este tipo de algoritmo tem complexidade