Questão Q194219

Question

Considere os seguintes algoritmos e suas complexidades na notação Big O:

- Algoritmo A: O(log n)
- Algoritmo B: O(n²)
- Algoritmo C: O(n . log n)

Considerando-se o pior caso de execução destes algo- ritmos, é correto afirmar que o algoritmo

Answer

Para quem nunca tinha ouvido falar desta notação, assim como eu.... ai vai....

Notação O Grande (também conhecida como big O notation, no inglês , notação Landau, notação Bachmann–Landau e notação assintótica) descreve o comportamento limitante de uma função quando o argumento tende à um determinado valor ou ao infinito, geralmente em termos de funções mais simples. A notação O Grande Big permite que seus usuários simplifique funções para que se concentrem em suas taxas de crescimento: Funções diferentes com a mesma taxa de crescimento podem ser representadas usando a mesma notação O.
Apesar de ser desenvolvida como parte da matemática pura, atualmente esta notação é comumente utilizada na análise de algorítimos para descrever o uso de recursos computacionais realizado por um determinado algoritmo a partir da análise da complexidade do tempo de execução utilizando a análise do pior caso, caso médio ou melhor caso.

Answer

Resposta certa: letra D

A complexidade de algoritmos é muito importante para avaliar o tempo de execução de qualquer algoritmo. Para responder a questão podemos considerar, por exemplo, n = 100.
Então:

algoritmo A -> O(log n) = log 100 = 2, onde a base é 10, 10² = 100;

algoritmo B -> O(n²) = 100² = 10000;

algoritm C -> O(n log n ) = 100 log 100 = 100x2 = 200,
Logo, tempo de B > tempo de C > tempo de A, B é o que tem a pior eficiência.

Answer

Uma pequena "correção" na resposta do colega Caracol (que não invalida de forma alguma a argumentação dele).

A complexidade O(log n) se refere à base 2, e não à 10.

Alguns exemplos de algoritmos que possuem complexidade O(log n) são as buscas binárias e buscas em uma árvore binária de busca que esteja balanceada (árvores binárias não balanceadas vão ter complexidade no pior caso de O(n)).
Essa complexidade é conseguida, no caso das buscas, em sempre "eliminar" a metade do total atual da lista em uma única iteração, ou seja, na primeira iteração elimina 50% do total, na segunda 75% (50% + 25%), terceira 87,5%(50% + 25% + 12,5%) e assim vai até achar o resultado. Dessa forma o número máximo de iterações sempre será, no pior caso, um logarimo na base 2 de n, onde n é igual ao número máximo de elementos contidos na lista.
Por exemplo, realizar uma busca binária em um vetor de 8 posições. Na primeira iteração serão eliminados 4 valores, na segunda 2 e na terceira 1. Caso não seja achado o valor o algoritmo terminará, pois não haverá mais nem um campo a ser pesquisado. Então a complexidade dessa busca é no pior caso de 3 iterações, que é exatamente o valor de log8 na base 2. Pois 2³ = 8.
Vale ressaltar que para ser possível alguma forma de pequisa binária a lista deve estar ordenada.

Nesse link abaixo contém uma boa apostila sobre complexidade de algoritmos.
http://www.ime.usp.br/~song/mac5710/slides/01complex.pdf

Answer

Pessoal,

Pelas alternativas e pela figura do link abaixo percebemos que o algoritmo B é polinomial, ou seja, é o menos eficiente ou mais complexo:

https://dl.dropbox.com/u/71196419/ComplexidadeAlgoritmos.jpg

Answer

Ordenando-os por eficiência:

1 Algoritmo A: O(log n)

2 Algoritmo C: O(n . log n)

3 Algoritmo B: O(n2)

O A é visivelmente mais eficiente pq C é o valor de A multiplicado por N, ou seja: C é N vezes maior que A.

Answer

- Algoritmo A: O(log n) -----> logn (MAIS EFICIENTE DAS 3)
- Algoritmo B: O(n2) -----> n2 (MENOS EFICIENTE DAS 3)
- Algoritmo C: O(n . log n) -----> nlogn ( TA NO MEIO)

(A) A é o menos eficiente. (É O MAIS EFICIENTE)
(B) C é o menos eficiente. (E A MENOS EFICIENTE)
(C) A não é o mais eficiente nem o menos eficiente. (É A MAIS EFICIENTE)
(D) B é o menos eficiente. (CORRETO!!!!)
(E) C é o mais eficiente. (É A MENOS EFICIENTE)

--------------------------------------------------------------------------------------------------------------------------------------

A tabela que tem que ter tatuada no cerebro:

OBS1. A complexidade vai aumentando, ou seja, CONSTANTE 1 é a menos complexa, já a exponencial é a mais complexa.

OBS2. A eficiência vai diminuindo, ou seja, CONSTANTE 1 é a mais eficiente, já a exponencial é a menos eficiente.

--------------------------------------------------------------------------------------------------------------------------------------

SóProvas

Continue usando...

O que está incluso