Solucionado (ver solução)
Solucionado
(ver solução)
12
respostas

[DÚVIDA] Algoritmos I: Selection, Insertion e Introdução a Análise - Aula 6. Algoritmos: Entrada e saída

Tenho 3 questões quanto à análise assintótica.

1a) Por que na análise assintótica do método buscaMenor, não consideramos a atribuição do valor da variável inicio à variável maisBarato como uma operação para considerar no custo do método?

2a) Existe algum material mais aprofundado sobre o assunto análise assintótica? Não sabia que existia esse tipo de análise!

3a) Existe algum plugin do Eclipse/IntelliJ ou framework Java que faz a análise assintótica do código automaticamente?

12 respostas

1) deveria ter sido considerada :P

2) minha melhor indicação é Introducao aos Algoritmos, do Cormen e galertinha do MIT: http://www.submarino.com.br/produto/111052655/livro-algoritmos-teoria-e-pratica

O preço é um soco no estomago. O artigo do wikipedia é um pouco confuso.

3) não conheço. googlei e não achei. de qualquer maneira imagino que apenas algoritmos bem simples poderiam ser analisados dessa forma

ps: muito legal você ter se interessado. esse é o caminho do verdadeiro cientista da computação.

Acho que é porque na análise assintótica você fica só com o caso de maior ordem. Estou fazendo esse curso para revisar essa parte e vou chegar nessa parte em breve. De qualquer forma parabéns por ter identificado!

Só acrescentar ao que o Paulo falou, algumas pessoas me disseram que a tradução em português é defasada. Então recomendo a versão em inglês (estou economizando para comprar, é mais cara ainda :( )

Henrique tem razão. assintoticamente aquele ali não vai mudar o resultado final, mas deveria ter sido falado e analisado.

Ah sim, mas errar é humano Paulo, acho que nem foi erro, só uma informação omitida. A propósito (completamente fora do tópico), prazer em conhecê-lo! :D

solução!

Henrique e Paulo, muito obrigado pelos retornos. Eu tenho esse livro do Cormen. Comprei há um tempo atrás pois já vislumbrava a necessidade total de conhecimento em algoritmo. Acho que tem certos conhecimentos que diferem um programador comum de um ninja. Eu quero ser Ninja (hahahahahahaha).

Valeuzáço! Se o livro abrange o assunto, irei comê-lo em breve. Apenas não comecei a ler já pois estou estudando algumas tecnologias antes por conta do projeto atual que estou atuando, mas vou começar a ler logo logo.

Show Daniel e eu concordo contigo. Sou meio que novo na área, mas essa parte de estrutura de dados é algo que quero ter comigo. Acho que isso faz uma baita diferença quando eu tiver a chance de trabalhar com sistemas mais complexos que exijam performance.

Henrique, eu fiz um teste para o Spotify na Suécia, e outro para uma empresa alemã que deixaram bem evidente uma coisa. Considerando que os países europeus e estados unidos em geral, trabalham com tecnologia de ponta, de longe investir na área de processamento de dados performáticos, Inteligência Artifical, Machine Learning, etc., são os assuntos que vão ficar cada vez mais evidência no futuro. Um primo meu compartilhou um post em um blog há pouco tempo dizendo sobre isso, que o mundo dos webservices vai deixar de ser o "bam bam bam". Se não for pra usar pra resolver problemas realmente graúdos, não convém ficar só nesse ambiente, tem de começar a ir pra coisas mais complexas.

Aproveitando pra não criar mais um tópico:

O algoritmo N*log(N) se chama algoritmo linearítmico?

Nunca ouvi essa terminologia. Quando falamos apressadamente, normalmente falamos "algoritmo nlogn".

Eu encontrei essa terminologia no Wikipedia https://pt.wikipedia.org/wiki/Grande-O. Lá tem uma tabela com os nomes dos tipos de algoritmos usando a notação O:

O(n log n) = O(log n!) => linearítmico, loglinear, ou quasilinear: Rodar uma Transformada Rápida de Fourier; heapsort, quicksort (melhor caso e caso médio), ou merge sort

Seria isso?

É isso sim, mas realmente em 8 anos de faculdade de ciencia da computacao nunca escutei falarem assim. Sempre "nlogn". Assim como "grande O", e sim "notação O". Pode ser bairrismo de São Paulo, ou o artigo do wikipedia estar fortemente ligado ao português de portugal. Mas não me preocuparia com esses nomes.

Paulo, muito provável ser bizarrice do Wikipedia. Sempre escuto que lá tem muita informação lixo. Na realidade é só pra confirmar se interpretei o tipo de nomenclatura correto, porque o importante é entender o conceito, o nome é só um detalhe. Mas valeu pelo toque, agora sei que o jeito certo é chamar de " N log(N)" mesmo. Valeuzáço! :)