Questões de Complexidade de Algoritmos (Algoritmos e Estrutura de Dados)

Limpar Busca
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.
  • A Pior caso: O(n2); melhor caso: O(n).
  • B Pior caso: O(n lg n); melhor caso: O(n).
  • C Pior caso: O(n); melhor caso: O(n + m).
  • D Pior caso: O(n lg n); melhor caso: O(n + m).
  • E Pior caso: O(n2); melhor caso: O(n lg n).
Um algoritmo que apresenta a menor complexidade dentre todos os possíveis algoritmos para resolver o mesmo problema é considerado um algoritmo
  • A matriz.
  • B ótimo.
  • C operacional.
  • D simplificado.
  • E natural.

Considere o trecho de código abaixo para multiplicação de matrizes quadradas n x n,



Qual a complexidade de pior caso deste algoritmo?

  • A O(n2 )
  • B O(n3 )
  • C O(n)
  • D O(logn)

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?

  • A Problema do caminho mínimo com complexidade O (m + n log n) em que m é o número de arestas e n é o número de vértices.
  • B Problema do caminho mínimo com complexidade O (n!) em que n é o número de vértices.
  • C Problema da mochila com complexidade O (m * n) em que m é o número de arestas e n é o número de vértices.
  • D Problema da mochila com complexidade O (m!) em que m é o número de arestas.

O Quick-Sort é considerado o algoritmo de ordenação baseado em comparação mais eficiente, mas em alguns casos sua complexidade é igual ao do Bubble-Sort. Assinale a alternativa que indica a complexidade do Quick-Sort quando o vetor está ordenado em ordem decrescente:

  • A O(n)
  • B O(n^2 log n)
  • C O(n log n)
  • D O(n^2)
  • E O(log n)