Está correta minha colocação? Obrigadíssima 
Pode postar a tarefa inteira por favor? Tá estranho isso aí… Vc encontrou seis polinômios que representam a execução de um determinado algoritmo em seis situações distintas, os colocou em ordem e classificou qual o melhor, pior e médio? Foi isso?
Outra interpretação possível pelo o que vc postou é que o exercício fornece esses polinômios que, aliás, deveriam ser fornecidos/apresentados como funções, e vc precisa classificá-los. Usando um n relativamente “grande”, por exemplo, 100. Vc teria respectivamente, para cada um dos seus polinômios, os valores 3020101, 6050000, 9000300, 50700, 70000, 2200. Para n igual a 2 já é possível ver que o polinômio 9n^3 + 3n representa a função que cresce mais rápido nessas seis mostradas.
2 curtidas
1.Utilizando as definições para as notações assintóticas, classifique as seguintes expressões em ordem decrescente de complexidade, em seguida, classifique qual seria o melhor caso, caso médio e o pior caso
- 9n³ + 3n
2)6n³ + 5n² - 5n² + 7n
4)22n
5)7n²
6)3n³ + 2n² + n + 1
Obrigada pela atenção, estou me esforçando , mas, esta disciplina Estrutura de Dados, estou correndo atrás.
Oi Amanda, vendo o enunciado, ainda continuo achando esquisito. O que o seu professor chama de “definições para as notações assintóticas”? Digo isso pois, classificar uma função, não uma expressão como é pedido, assintoticamente pode implicar um conjunto de notações: O(T(n)), Ω(T(n)), Θ(T(n)), o(T(n)), ω(T(n)) e θ(T(n)). Cada uma dessas notações indicam um conjunto de funções que detêm um determinado tipo de característica limitante. Por exemplo, a notação ômicron maiúsculo (“Ózão” / O / Big-Oh) de uma função qualquer indica o conjunto de todas as funções que são limitadas superiormente por uma função “arbitrária” ao se tender o tamanho do problema (normalmente n) ao infinito.
Normalmente usamos a notação O indicando o menor “tipo” de função que limita superiormente a função que estamos analisando, permitindo assim que tenhamos essa ideia de que se T(n) é O(n^2), por mais que aumentemos o n essa função nunca terá um crescimento menor do que quadrático. Sendo assim, a notação O pode ser usada para qualquer limitante superior… Poderíamos até falar que se T(n) = 2n^2 + 3n + 1, T(n) é O(n^3), mas não fazemos isso.
Voltando ao seu problema. Se inferirmos que seu professor quis dizer que as funções (não expressões) são:
T(n) = 9n³ + 3n
T(n) = 6n³ + 5n²
T(n) = 5n² + 7n
T(n) = 22n
T(n) = 7n²
T(n) = 3n³ + 2n² + n + 1
E levarmos ao pé da letra as definições assintóticas, teríamos para cada item, assumindo também que ele está falando da notação O, respectivamente O(n^3), O(n^3), O(n^2), O(n), O(n^2) e O(n^3). O que o seu professor provavelmente quer e não soube explicar (talvez nem ele saiba infelizmente) é que você coloque as funções (não expressões) em ordem decrescente de acordo com o crescimento delas. Para isso, basta substituir n por algum valor, como eu já disse, e ver quem cresce mais. Se fizer isso, o correto seria:
9n³ + 3n > 6n³ + 5n² > 3n³ + 2n² + n + 1 > 5n² + 7n > 7n² > 22n
Agora caso médio, pior e melhor, acho que ele quer as extremidades dessa ordenação e algo entre o meio. O que não faz muito sentido tbm…
1 curtida
Obrigadíssima. Lamentável, um assunto tão importante, que indica ao programador iniciante como elaborar algoritmos mais eficientes, e estou perdida, tirei o final de semana para assistir vários vídeos no youtube. Agradeço sua atenção e ao tempo dedicado 
1 curtida