Questões de Concurso Comentadas 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?

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:

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

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.

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

A ideia da ordenação por bolha (Bubble Sort) é percorrer o vetor de elementos sequencialmente e, em cada passagem comparar cada elemento com seu sucessor, fazendo-o chegar ao topo da sequência. Dado que n é o número de elementos do vetor, a complexidade do pior caso desse algoritmo é

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: 

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 2ⁿ . V) A complexidade do algoritmo de pesquisa binária é logarítmica. Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

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) = n² e f(n) = (n+1)² temos que g(n) é O(f(n)) e f(n) é O(g(n)). V) Se g(n) = 2ⁿ⁺¹ e f(n) = 2ⁿ temos que g(n) = O(f(n)). Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

Considere a função de complexidade f(n) = 3n³ + 4n² +2n. Selecione a opção abaixo contendo o menor valor para a constante c, c>0, para que g(n) = c.n³ domine assintoticamente f(n), para n>= 1.

O tempo necessário de pesquisa em uma árvore de busca binária varia de acordo com a estrutura dessa árvore. Em árvores de busca binária, o intervalo de variação de tempo de busca é entre 

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? 

A respeito do alinhamento múltiplo de sequências, é correto afirmar:

São programas de bioinformática usados para alinhamento de sequências curtas de nucleotídeos, provenientes de sequenciadores de segunda geração:

Na análise de complexidade de algoritmos, em que o interesse é restrito a valores assintóticos e se desconsidera as constantes multiplicativas e aditivas, qual é o número de passos a ser considerado na expressão 2(n²-1) + 10n³?