SóProvas

ID
2482060
Banca
FGV
Órgão
IBGE
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

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: 

Alternativas
Comentários

  • Pensei que seria logarítmica.

  • 1- f(n) = O(1) – Complexidade constante

    2- f(n) = O(log n) – Complexidade sub-linear ou logarítmica

    3- f(n) = O(n) – Complexidade linear

    4 - f(n) = O(n log n) – Sub-divisão de problema (Exe.: MergeSort e QuikSort)

    5 - f(n) = O(n^2) – Complexidade polinomial

    6 - f(n) = O(2^n) – Complexidade exponencial

    7 - f(n) = O(n!) – Complexidade fatorial

     

    Fonte: http://www.ebah.com.br/content/ABAAAAygYAA/algoritimos

  • Prezados,

    Temos a seguinte relação de funções com taxas de crescimento :

    -Tempo constante: O(1) (raro)
    -Tempo sublinear (log(n)): muito rápido (ótimo)
    -Tempo linear: (O(n)): muito rápido (ótimo)
    -Tempo nlogn: Comum em algoritmos de divisão e conquista.
    -Tempo polinomial n^k : Freqüentemente de baixa ordem (k ≤ 10), considerado eficiente.
    • Tempo exponencial: 2n, n!, n^n considerados intratáveis 

    Portanto a alternativa correta é a letra B

  • Força Guerreiro!!!!!!