tag:blogger.com,1999:blog-6306509703738480474.post2827198529687697727..comments2023-09-30T16:03:16.552-03:00Comments on Brain Dump: O algoritmo mais rápido do oesteRicardo Bittencourthttp://www.blogger.com/profile/17393980440854756685noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6306509703738480474.post-7233466620324654392010-03-26T10:37:32.615-03:002010-03-26T10:37:32.615-03:00Eu coloquei o super otimizador aqui: http://www.ri...Eu coloquei o super otimizador aqui: http://www.ricbit.com/code/opt.cRicardo Bittencourthttps://www.blogger.com/profile/17393980440854756685noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-34584221234306680882010-03-26T07:24:29.831-03:002010-03-26T07:24:29.831-03:00Primeiramente gostaria de parabenizá-lo pelo site,...Primeiramente gostaria de parabenizá-lo pelo site, dificilmente se encontra sites com conteúdos tão bons na internet.<br />Eu gostaria de saber se o super otimizador é disponível pois não encontrei o opt.c para download.<br /><br />Alexandre Felipe Muller de SouzaAlexandrehttps://www.blogger.com/profile/09070259938391063277noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-64857410586897196722010-03-25T19:54:43.085-03:002010-03-25T19:54:43.085-03:00Ela é O(n) também né? Eu estava procurando as solu...Ela é O(n) também né? Eu estava procurando as soluções O(0) :)Ricardo Bittencourthttps://www.blogger.com/profile/17393980440854756685noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-26841699320319736042010-03-25T19:47:28.100-03:002010-03-25T19:47:28.100-03:00Você chegou a testar minha sugestão do memoize(qui...Você chegou a testar minha sugestão do memoize(quicksort) ?muriloqhttps://www.blogger.com/profile/14431133035347007574noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-35548416764784839222010-03-25T16:49:28.239-03:002010-03-25T16:49:28.239-03:00Ola
A gente sempre usa isso pro heap implicito, a...Ola<br /><br />A gente sempre usa isso pro heap implicito, ate pq tambem é muito facil de manipula-lo. Mas se voce precisar mexer nessa arvore estruturada como vetor, tera muito problema: para acertar os links muitas operacoes que custariam O(1) passarao a custar O(n).Paulo Silveirahttps://www.blogger.com/profile/06527352519775026268noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-88764607209283536662010-03-25T11:55:41.463-03:002010-03-25T11:55:41.463-03:00Ah sim, quando a árvore não é perfeita, você preci...Ah sim, quando a árvore não é perfeita, você precisa ser mais esperto . O algoritmo é assim: se por algum motivo você chegar em um nó cujo valor é maior que N, então é certeza que o nó à direita também não vai existir. Daí você automaticamente propaga para o nó à esquerda e faz o loop. Isso não muda o caminho máximo da raiz até a folha, que continua O(log n) no pior caso; mas o custo de descer um nível, que era O(1) na árvore perfeita, tem pior caso O(log n) na árvore incompleta.Ricardo Bittencourthttps://www.blogger.com/profile/17393980440854756685noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-40604927053963551952010-03-25T11:12:47.939-03:002010-03-25T11:12:47.939-03:00É verdade. Mas o esquema (start,end) mantém um mel...É verdade. Mas o esquema (start,end) mantém um melhor balanceamento médio.<br /><br />Continuando no papel de advogado do diabo :), existe alguns detalhes para acessar right(x). A árvore à esquerda é sempre completa. Entretanto, a árvore à direita pode ser estranha. Veja, por exemplo, uma árvore com 9 elementos. O elemento no índice 9 deveria ser o filho direito do índice 8, correto? Entretanto, right(8) é 12, que não existe nesta árvore.<br /><br />Para resolver isto, acho que bastaria iterar "recursivamente" (algo como x=right(x)), até chegar a um índice existente. Mas também é uma desvantagem desta abordagem.Anonymoushttps://www.blogger.com/profile/10955791462082388350noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-69161969517074469612010-03-25T08:08:06.665-03:002010-03-25T08:08:06.665-03:00@Eraldo: Sure, assim funciona também. Eu não usei ...@Eraldo: Sure, assim funciona também. Eu não usei esse método porque eu queria achar uma função left() e right() que dependesse apenas do índice. Montando a árvore desse jeito, a estrutura isomórfica ao ponteiro é a tupla (start,end), e aí você gasta o dobro de memória por ponteiro hehe.<br /><br />@PV: Eu participei da Maratona quando estava na faculdade, há muito, muito tempo atrás :)Ricardo Bittencourthttps://www.blogger.com/profile/17393980440854756685noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-56828365696955698902010-03-25T01:26:32.439-03:002010-03-25T01:26:32.439-03:00Você já chegou a participar de alguma Maratona de ...Você já chegou a participar de alguma Maratona de Programação da SBC? É bem jóia e trabalha com problemas computacionais resolvidos de maneiras criativas :).PVhttps://www.blogger.com/profile/15622611803183663003noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-7203034928286112332010-03-25T01:10:07.250-03:002010-03-25T01:10:07.250-03:00Parabéns! Você acabou de inventar a busca binária ...Parabéns! Você acabou de inventar a busca binária (em um vetor ordenado). ;)<br /><br />Agora, falando sério. Acho que você deu uma volta muito maior do que a necessária. No próprio artigo você cita uma solução mais simples:<br /><br /> middle = start + (end-start) / 2<br /> return (vector[middle], <br /> partition(start, middle-1), <br /> partition(middle+1, end))<br /><br />Este algoritmo pode ser facilmente traduzido para uma estrutura implícita. Defina uma árvore implícita como dois índices do vetor: start e end (usando os mesmos termos do algoritmo). A raiz de uma árvore (start,end) é middle=(start + (end-start) / 2). A sub-árvore esquerda desta árvore é (start,middle-1) e a direita é (middle+1,end). Pronto! O que acha? Concorda?<br /><br />Bom, mas como você observou, isto só serve pra busca (binária).Anonymoushttps://www.blogger.com/profile/10955791462082388350noreply@blogger.comtag:blogger.com,1999:blog-6306509703738480474.post-66052782541359880542010-03-25T00:36:08.541-03:002010-03-25T00:36:08.541-03:00sem palavras...
parabéns pelo textosem palavras...<br /><br />parabéns pelo textoDavid Kwasthttps://www.blogger.com/profile/00722530786608289032noreply@blogger.com