pessoal, estudando aqui me veio uma dúvida.
por exemplo, se eu tenho um algoritmo com complexidade n^2 e outro com complexidade 10^n teria algum caso que seria melhor usar o algoritmo de complexidade 10^n se sim, então qual seria esse caso?
O algoritmo n^2 seria sempre mais eficiente teoricamente, porém se n for um valor muito pequeno e o algoritmo 10^n for muito mais simples (o que eu duvido que seja possível com uma complexidade dessas), você poderia escolher o algoritmo menos eficiente pra facilitar manutençao do código.
Lembrando que na vida real tudo isso depende. Essa complexidade é uma aproximaçao. E na prática há outros fatores que influenciam na escolha. Geralmente na dúvida você testa com valores reais pra saber se vale o que vale mais a pena.
1 curtida
deixa ver se entendi. então quer dizer que vai depender do valor da entrada. se for um valor muito grande um algoritmo por exemplo, de 3^n seria melhor do que um de n^8, certo?
Para os exemplos que você deu, a entrada nao afeta muito, vamos considerar vários valores de n (1,10,100,1000), nos seus exemplos temos:
nˆ2 = 1,100,10000,1000000
10^n = 10, 10_000_000_000, …
3 ^ n = 3, 59_049
n ^ 8 = 1, 100_000_000
Ou seja, pra qualquer praticamente qualquer valor de n, ter um n elevado a alguma coisa vai ser pior.
Na prática, você geralmente escolhe o que escala melhor, o que o número de operaçoes (ou espaço) vai aumentar menos de acordo com a entrada.
E claro, se a entrada for sempre um valor baixo, você escolhe o mais simples.
1 curtida
e se no caso for um valor mais alto, escolheria o de maior complexidade?
Nao, quanto maior o valor, pior fica para o algoritmo de maior complexidade… é só calcular a forma e ver como fica (veja meu exemplo com diferentes valores de n, como o algoritmo de pior complexidade fica com valores piores muito mais rápido)
1 curtida
então qual seria o caso que seria melhor utilizar um algoritmo de maior complexidade em detrimento do de menor?
Como eu disse acima, se a entrada for pequena e o algoritmo de maior complexidade for mais simples.
1 curtida
me desculpe, mas como assim mais simples?
Mais simples de entender.
Por exemplo, compare o algoritmo Bubble Sort com o Quick Sort.
Quick sort é muito mais eficiente mas também mais difícil de entender o que ele faz.
O Bubble sort nao é eficiente mas é bem intuitivo de entender porque ele funciona.
2 curtidas
No seu exemplo de n^2 ou 10^n, fica difícil dizer por que preferir um ou outro sem saber o que fazem ou quais outras características eles tem. Se somente essa métrica for usada, não há nenhum motivo para utilizar a versão 10^n.
Entretanto, existem outras considerações na escolha de um algoritmo, como memória usada, desempenho nos casos mais comuns do cenário (ex: se 99% das vezes ocorre o pior caso, talvez o algoritmo A seja melhor que o B, mesmo que B seja superior no melhor caso), uso de certas instruções do processador ou estruturas da memória, etc. Desempenho nem sempre é a única métrica a ser considerada, e em alguns casos nem é a principal.
Pegando o caso de algoritmos de ordenação, muitas aplicações dão preferência ao MergeSort no lugar do QuickSort, apesar do QuickSort ser famosamente mais rápido. Dentre os motivos, está o fato do MergeSort ser naturalmente estável (a posição inicial dos elementos é preservada se já estiverem em ordem), e pode ter melhor desempenho no pior caso sem a necessidade de ajustes (implementações mais simples do QuickSort precisam de ajustes pra superar o MergeSort no pior caso).
Abraço.
1 curtida