Question

A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes. Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência. Mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção.

A notação BIG O é utilizada para indicar a complexidade de algoritmos baseados em sua dominância assintótica. As funções a seguir são utilizadas normalmente para expressar complexidade.


- n²

- n³

- logN

- NlogN

Assinale a alternativa que apresenta a ordem crescente das funções em relação a sua complexidade.

Alternativas:

a)
n³ > n² > logN > NlogN

b)
NlogN < logN < n² < n³

c)
n² < n³ < NlogN < logN

d)
logN < NlogN < n² < n³

e)
n² > n³ > logN > NlogN

Answer 1

Resposta:

logN < NlogN < n² < n³

Alternativa d)

confirmado no AVA

Explicação:

Digamos que a sua entrada seja N=10, temos que:

log 10=1

N log 10 = 10

n² = 100

n³ = 1000