Gratidão pelo vídeo! só uma correção: dijkstra é: O(n^2+m) ou O(m*log2 m), ependendo de sua implementação, respectivamente, para grafos densos e grafos esparsos sendo N a quantidade de vértices e M a de arestas
@@tlsaulo9229 Se sua implementação usar heap binária, vc vai precisar inicializar e atualizar ela. Inicializar custa O(n), atualizar custa O(log n). Podemos simplificar a análise do dijkstra em duas partes: A extração do nó com menor distância (1) e a atualização das distâncias (2). A primeira parte vai custar O(n * log n), pq vc precisa extrair o nó da heap e essa extração pode ser feita até n vezes - uma pra cada vértice. Cada extração custa O(log n), pq extrair da heap significa remover o elemento mínimo e reorganizar a estrutura dela. A segunda etapa também custa O(log n) pra cada operação. A atualização das distâncias é feita para cada aresta, resultando em O(m * log n). No final, somando as duas etapas, vc fica com O((n+m) * log n).
Minha dissertação foi sobre economia dos transportes e eu penei para entender minimamente o funcionamento da biblioteca que usei para estimar tempos de deslocamento entre n pontos através de uma rede de ônibus. Sua explicação teria facilitado demais. Excelente vídeo!
Vídeo sensacional! Comecei a ler ontem o livro Arquitetura Limpa, e logo no começo o uncle bob menciona Dijkstra e seu algoritmo, não tinha ficado muito claro, para eu, como funcionava esse algoritmo, mas com esse vídeo abriu minha mente! Muito obrigado!
Você é foda, traz um vídeo sobre lock otimista, pessimista e database constraints, quando usar cada um, trade-offs com o objetivo de resolver problemas de concorrência
Muito bom e direto, minha recomendação seria fazer mais videos puxando algoritmos mais conhecidos ou algortimos de ordenação (heapsort, mergesort, etc)
brasil ta precisando de gente assim, por favor, quando tiver grandao seu canal nao deixe de fazer videos em portugues :) tem mt gente q ta começando no ingles tbm
Olá Augusto. Gostaria de te parabenizar pelo vídeo, uma forma bem prática de entender o algoritmo! Se for possível, gostaria de saber qual software você utiliza em seus vídeos. Seria o Excalidraw?
Muito legal seu canal, mano! São poucos canais que trazem um conteúdo mais acadêmico sobre programação... Os que estão em altam só falam sobre programação web, full stack, etc. Curso bacharelado em Matemática e produzo vídeos com um viés acadêmico (matemático) sobre Segurança da Informação, mais especificamente Criptografia. Agradeço se der uma olhada!
Cara, uma coisa que eu ainda não entendi sobre o algoritmo de dijkstra é que parece que existem duas implementações. Uma, como a do vídeo, onde ele simplesmente itera sobre todos os vértices e outra onde o algoritmo vai sempre passando pelo menor caminho, tipo, se o caminho A pra B é menor que o caminho de A pra C, então o algoritmo vai seguir aquele caminho. Alguém pode me explicar melhor? qual a melhor implementação?
Tem duas formas clássicas de implementar o algoritmo de Dijkstra: a primeira é uma versão simples que itera por todos os vértices a cada passo para encontrar o nó com a menor distância atual, fazendo uma busca linear. A segunda utiliza uma heap (fila de prioridade) pra armazenar os vértices e acessar diretamente o nó com a menor distância, "seguindo o menor caminho" em vez de iterar por todos os vértices. Geralmente, a versão com heap é melhor, pq tem complexidade O((n+m)logn) e é muito mais rápida pra grafos grandes. A primeira versão tem complexidade O(n^2 + m), pode ser melhor pra grafos pequenos ou densos.
Gratidão pelo vídeo! só uma correção: dijkstra é: O(n^2+m) ou O(m*log2 m), ependendo de sua implementação, respectivamente, para grafos densos e grafos esparsos
sendo N a quantidade de vértices e M a de arestas
Então porque tem vários artigos falando que é mlogn?
@@tlsaulo9229 Se sua implementação usar heap binária, vc vai precisar inicializar e atualizar ela. Inicializar custa O(n), atualizar custa O(log n). Podemos simplificar a análise do dijkstra em duas partes: A extração do nó com menor distância (1) e a atualização das distâncias (2). A primeira parte vai custar O(n * log n), pq vc precisa extrair o nó da heap e essa extração pode ser feita até n vezes - uma pra cada vértice. Cada extração custa O(log n), pq extrair da heap significa remover o elemento mínimo e reorganizar a estrutura dela. A segunda etapa também custa O(log n) pra cada operação. A atualização das distâncias é feita para cada aresta, resultando em O(m * log n). No final, somando as duas etapas, vc fica com O((n+m) * log n).
@@rafaelstutz8114não acho que é por aí nao. Vc está equivocado
@@tlsaulo9229 O(log(m)) = O(log(n)) pois O(m) = O(n^2) e log n^2 = 2 log n
meu sonho era achar algum canal brasileiro que abordasse diferentes tipos de algoritmos. Parabéns pelo trabalho bro
tem vários livros sobre isso
Tem vários vídeos de aulas de universidades gravadas durante a pandemia!
Minha dissertação foi sobre economia dos transportes e eu penei para entender minimamente o funcionamento da biblioteca que usei para estimar tempos de deslocamento entre n pontos através de uma rede de ônibus. Sua explicação teria facilitado demais. Excelente vídeo!
Sua didática é diferenciada, parabéns pelo conteúdo de qualidade!
seus conteúdos são muito bons, obrigada por compartilhar conosco!!
Ótimo video!
Estava lendo o livro Entendendo Algoritmos e com algumas complicações com isso aqui. Muito esclarecedor!
Vídeo sensacional! Comecei a ler ontem o livro Arquitetura Limpa, e logo no começo o uncle bob menciona Dijkstra e seu algoritmo, não tinha ficado muito claro, para eu, como funcionava esse algoritmo, mas com esse vídeo abriu minha mente! Muito obrigado!
Ótima explicação! Super didática!
Muito legal... Explanação simples e clara!
Você é foda, traz um vídeo sobre lock otimista, pessimista e database constraints, quando usar cada um, trade-offs com o objetivo de resolver problemas de concorrência
Sou fã e sempre serei! Voa jovem!
Muito bom e direto, minha recomendação seria fazer mais videos puxando algoritmos mais conhecidos ou algortimos de ordenação (heapsort, mergesort, etc)
up
+1 Inscrito, didático, massudo e explicativo
que trabalho incrível, adorei a explicação, obrigado por existir e fazer esse video
Muito interessante. Na faculdade não vi nem menção a esse algoritmo. Parabéns pelo conteúdo, ganhou um inscrito
Opa, estava lendo livro sobre isso essa semana, mas uma informação importante: Ele não resolve em O(n) mas sim O(n log n).
Vídeo bem interessante. Sucesso!
brasil ta precisando de gente assim, por favor, quando tiver grandao seu canal nao deixe de fazer videos em portugues :) tem mt gente q ta começando no ingles tbm
Muito bacana as always, Augusto. Quando possível, explique o algoritmo do Caixeiro Viajante
muito bommmmm!!! teu canal é muito necessário!
Q da hora cria uma playlist só com algoritmos aí fica bem mais fácil de ver tudo de uma vez
Pelo assunto acadêmico de algoritmo me inscrevi pelo acompanha, tópico específico seu Canal lógico
Mano, esse mano é daora demais!
Cacete, parece demais com a Sephirot arvore da vida da cabala
Eu aprendi essa bagaça pra fazer a prova de AED e depois deletei do cérebro. Bom vídeo.
Olá Augusto. Gostaria de te parabenizar pelo vídeo, uma forma bem prática de entender o algoritmo!
Se for possível, gostaria de saber qual software você utiliza em seus vídeos. Seria o Excalidraw?
Muito bom! Vlw guerreiro.
Braboo, parabéns
Muito legal seu canal, mano! São poucos canais que trazem um conteúdo mais acadêmico sobre programação... Os que estão em altam só falam sobre programação web, full stack, etc. Curso bacharelado em Matemática e produzo vídeos com um viés acadêmico (matemático) sobre Segurança da Informação, mais especificamente Criptografia. Agradeço se der uma olhada!
bom dia galego te amo obrigado pelo conteudo
A didática da ciências da computação não é muito boa, eles estão mais preocupados em cobrar do que ensinar, mas com você foi tranquilo. Valeu
Cara, uma coisa que eu ainda não entendi sobre o algoritmo de dijkstra é que parece que existem duas implementações. Uma, como a do vídeo, onde ele simplesmente itera sobre todos os vértices e outra onde o algoritmo vai sempre passando pelo menor caminho, tipo, se o caminho A pra B é menor que o caminho de A pra C, então o algoritmo vai seguir aquele caminho. Alguém pode me explicar melhor? qual a melhor implementação?
Tem duas formas clássicas de implementar o algoritmo de Dijkstra: a primeira é uma versão simples que itera por todos os vértices a cada passo para encontrar o nó com a menor distância atual, fazendo uma busca linear. A segunda utiliza uma heap (fila de prioridade) pra armazenar os vértices e acessar diretamente o nó com a menor distância, "seguindo o menor caminho" em vez de iterar por todos os vértices. Geralmente, a versão com heap é melhor, pq tem complexidade O((n+m)logn) e é muito mais rápida pra grafos grandes. A primeira versão tem complexidade O(n^2 + m), pode ser melhor pra grafos pequenos ou densos.
que programa o senhor esta usando caba? toca de falar pro padrinho né
Q jeito
Good!
Comecei a assistir pra saber o que era e na vdd já sabia. É simplesmente otimização matemática 😮