não estou a conseguir entender como é obtida a complexidade deste algoritmo.
O algoritmo de Dijkstra tem a complexidade de O(|V|^2 + |E|), mas não entendo como esse valor é obtido.
A linha 2-4 é executado V vezes.
A linha 6 é executada V vezes, porque consiste em copiar todos os vértices para Q.
A linha 7-16 é executada V vezes.
A linha 12-16 é executada E vezes.
Como se pode concluir que este algoritmo têm essa complexidade?
[Algorithm]
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible from source
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return dist[]
É porque a linha 8 é O(V) também, ou seja, para extrair o mínimo demora O(V). Porém, existem EDs que extraem o mínimo mais rápido, dai a complexidade do algoritmo fica diferente. Mas para a sua pergunta a explicação é a linha 8 mesmo.
Engraçado que na faculdade ficam ensinando essas coisas aos montes… eu me lembrei de implementar isso mas nunca usei na vida real… assim como milhares de coisas que se ensinam na faculdade. As únicas coisas que uso em termos profissionais foram as linguagens de programação.
Uma dúvida… alguém aqui implementa isso profissionalmente? Tirando professores?
Não seria melhor as faculdades ensinarem coisas práticas? Pois acho que aprender Java, C++ ou C# BD e etc leva o mesmo tempo para aprender esses algoritmos que pouquíssimas pessoas implementam e quando precisam, pegam algo pronto. Só que as linguagens não dá para pegar pronto, e sim precisam de muito estudo e prática.
É aquela velha história, tem muito conhecimento sendo ensinado para pouco uso. O tempo de aprendizado de qualquer coisa é igual na média… só que para otimizar deveríamos ensinar algo que será aproveitado e não algo que 90% das pessoas ou mais vão esquecer…
**Isso no Brasil é claro, se fosse nos EUA o berço onde tudo é inventado, ensinar isso seria muito útil, pois as empresas privadas iriam contratar com certeza para melhorarem e inventarem algo novo… já no Brasil é outros quinhentos… o Brasil é famoso por commodities e usar tecnologia dos outros… não adianta querer ensinar elefante ser magro… é melhor ensinar o elefante a ser um elefante mesmo…
[quote=Felipe Kan]Engraçado que na faculdade ficam ensinando essas coisas aos montes… eu me lembrei de implementar isso mas nunca usei na vida real… assim como milhares de coisas que se ensinam na faculdade. As únicas coisas que uso em termos profissionais foram as linguagens de programação.
Uma dúvida… alguém aqui implementa isso profissionalmente? Tirando professores?
Não seria melhor as faculdades ensinarem coisas práticas? Pois acho que aprender Java, C++ ou C# BD e etc leva o mesmo tempo para aprender esses algoritmos que pouquíssimas pessoas implementam e quando precisam, pegam algo pronto. Só que as linguagens não dá para pegar pronto, e sim precisam de muito estudo e prática.
É aquela velha história, tem muito conhecimento sendo ensinado para pouco uso. O tempo de aprendizado de qualquer coisa é igual na média… só que para otimizar deveríamos ensinar algo que será aproveitado e não algo que 90% das pessoas ou mais vão esquecer…
**Isso no Brasil é claro, se fosse nos EUA o berço onde tudo é inventado, ensinar isso seria muito útil, pois as empresas privadas iriam contratar com certeza para melhorarem e inventarem algo novo… já no Brasil é outros quinhentos… o Brasil é famoso por commodities e usar tecnologia dos outros… não adianta querer ensinar elefante ser magro… é melhor ensinar o elefante a ser um elefante mesmo… [/quote]
Cara, concordo totalmente com vc. Mas acho que o princípio das universidades, principalmente as federais, é de formar cientistas e não mão de obra pro mercado. A explicação a meu ver é esta.
[quote=Felipe Kan]Engraçado que na faculdade ficam ensinando essas coisas aos montes… eu me lembrei de implementar isso mas nunca usei na vida real… assim como milhares de coisas que se ensinam na faculdade. As únicas coisas que uso em termos profissionais foram as linguagens de programação.
Uma dúvida… alguém aqui implementa isso profissionalmente? Tirando professores?
Não seria melhor as faculdades ensinarem coisas práticas? Pois acho que aprender Java, C++ ou C# BD e etc leva o mesmo tempo para aprender esses algoritmos que pouquíssimas pessoas implementam e quando precisam, pegam algo pronto. Só que as linguagens não dá para pegar pronto, e sim precisam de muito estudo e prática.
É aquela velha história, tem muito conhecimento sendo ensinado para pouco uso. O tempo de aprendizado de qualquer coisa é igual na média… só que para otimizar deveríamos ensinar algo que será aproveitado e não algo que 90% das pessoas ou mais vão esquecer…
**Isso no Brasil é claro, se fosse nos EUA o berço onde tudo é inventado, ensinar isso seria muito útil, pois as empresas privadas iriam contratar com certeza para melhorarem e inventarem algo novo… já no Brasil é outros quinhentos… o Brasil é famoso por commodities e usar tecnologia dos outros… não adianta querer ensinar elefante ser magro… é melhor ensinar o elefante a ser um elefante mesmo… [/quote]
Os algoritmos são importantes, pois eles são as ferramentas que temos para resolver problemas. Eu não uso o Dijkstra no meu dia a dia, mas GAs e RNAs utilizo bastante, porque trabalho com imagens digitais. Se um dia eu precisar do Dijkstra, posso utiliza-lo para resolver um problema.
Por isso as universidades estão mais preocupadas em se passar fundamentos para os alunos.
Linguagem de programação se aprende lendo livros, e são apenas o porta voz de algoritmos.
Em qualquer Universidade do mundo tem essa mesma filosofia, até mais que no Brasil. Quando entrei na faculdade o auge do negócio era Clipper. Se tivessem focado nele, eu já formaria defasado, porque formei no auge do Delphi e VB.
E uma coisa é fato: todos os meus amigos que se saíam bem nesses algoritmos complexos da faculdade hoje são excelentes desenvolvedores em qualquer linguagem que se deparam. Os que não gostavam, mesmo sendo bons de linguagens do momento, ou viraram programadores meia boca ou ficaram bons profissionais de outras áreas.
[quote=marcosalex]Em qualquer Universidade do mundo tem essa mesma filosofia, até mais que no Brasil. Quando entrei na faculdade o auge do negócio era Clipper. Se tivessem focado nele, eu já formaria defasado, porque formei no auge do Delphi e VB.
E uma coisa é fato: todos os meus amigos que se saíam bem nesses algoritmos complexos da faculdade hoje são excelentes desenvolvedores em qualquer linguagem que se deparam. Os que não gostavam, mesmo sendo bons de linguagens do momento, ou viraram programadores meia boca ou ficaram bons profissionais de outras áreas.[/quote]
E você?
[quote=pedroroxd][quote=marcosalex]Em qualquer Universidade do mundo tem essa mesma filosofia, até mais que no Brasil. Quando entrei na faculdade o auge do negócio era Clipper. Se tivessem focado nele, eu já formaria defasado, porque formei no auge do Delphi e VB.
E uma coisa é fato: todos os meus amigos que se saíam bem nesses algoritmos complexos da faculdade hoje são excelentes desenvolvedores em qualquer linguagem que se deparam. Os que não gostavam, mesmo sendo bons de linguagens do momento, ou viraram programadores meia boca ou ficaram bons profissionais de outras áreas.[/quote]
E você?[/quote]
Eu que te pergunto. Se te pedissem para desenvolver um motor, para um sistema que realizasse um data mining em um banco de dados, ou um sistema de navegação para carro ou avião, ou até mesmo gps, você estaria apto a desenvolver?
A resposta é não, se não tiver conhecimento de algoritmos.
Mas quando for fazer um curso de tecnologia, seja de engenharia, ciência, etc… pode ter certeza que vai se deparar com esses algoritmos. Se puder absorver o máximo desse conhecimento, vai poder trabalhar em qualquer área.
Não leva pro lado pessoal o que eu disse. Estou passando a experiência que tive quando estudava. Muita gente acha que computação e tecnologia é linguagem de programação, e isso não é verdade.
[quote=lavh]Pq vcs não vão discutir isso em outro tópico, e deixam esse somente com o seu intuito inicial?
O título aqui é: “Complexidade do algoritmo de Dijkstra” e não “Utilidade de estudar algoritmos de grafos”[/quote]
Porque gastou seu tempo postando isso?
Então comece dando exemplo, poste sobre o tópico.