Faz mais vídeos por favor! Sua explicação em 13 minutos fez eu entender mais do que 1 mês com o meu professor, e se duvidar vai acabar o semestre e eu não vou entender nem 1 virgula com a explicação dele.
Oi professora! Gostei muito da aula :). Tenho uma dúvida, no exemplo 2 no primeiro for ficou 2(n+1) mas não deveria ser 2n... não entendi. Grata pela atenção.
E quando o método é recursivo, como faço? No If a condição de parada é se a posição for par correto, Custo = 1? Por fazer uma comparação uma vez. No Else não sei como medir o custo. Me ajuda por favor. int q1(inf[ ] vet, obg pos){ If(pos== vet.length/2) return vet[ pos]; Else return (vet[pos] + vet[ver.lenght-1-pos] + q1(vet, pos+1)); }
Duvida Urgente!!! Se abaixo de um if tiver um retorno o custo desta operação abaixo será 1 no pior caso,por exemplo: for(...) --> custo 2(n+1) if(..) --> custo n return true; --> custo no pior caso = 1 ou N
Se dentro do if tiver um retorno, o fato dele entrar no if na primeira vez será considerado o melhor caso, e aí for(...) --> custo 2 if(..) --> custo 1 return true; --> custo 1 O pior caso é ele nunca entrar no if for(...) --> custo 2(n+1) if(..) --> custo n return true; --> 0
Esse trecho de algoritmo é quadrático, pois temos um comando de repetição dentro de outro (for dentro de while). Mas para fazer o cálculo exato, é necessário saber o número mínimo e máximo de vértices adjacentes de cada nodo.
é mais ou menos assim o algoritmo que tenho: int V;// No. of vertices //An Array of List which contains //references to the Adjacency List of //each vertex List adj[]; long tempoInicial = System.currentTimeMillis(); public Graph(int V)// Constructor { this.V = V; adj = new ArrayList[V]; for(int i = 0; i < V; i++) adj[i]=new ArrayList(); } // function to add an edge to graph public void addEdge(int u,int v) { adj[u].add(v); } // prints a Topological Sort of the complete graph public void topologicalSort() { // Create a array to store indegrees of all // vertices. Initialize all indegrees as 0. int indegree[] = new int[V]; // Traverse adjacency lists to fill indegrees of // vertices. This step takes O(V+E) time for(int i = 0; i < V; i++) { ArrayList temp = (ArrayList) adj[i]; for(int node : temp) { indegree[node]++; } } // Create a queue and enqueue all vertices with // indegree 0 Queue q = new LinkedList(); for(int i = 0;i < V; i++) { if(indegree[i]==0) q.add(i); } // Initialize count of visited vertices int cnt = 0; // Create a vector to store result (A topological // ordering of the vertices) Vector topOrder=new Vector(); while(!q.isEmpty()) { // Extract front of queue (or perform dequeue) // and add it to topological order int u=q.poll(); topOrder.add(u); // Iterate through all its neighbouring nodes // of dequeued node u and decrease their in-degree // by 1 for(int node : adj[u]) { // If in-degree becomes zero, add it to queue if(--indegree[node] == 0) q.add(node); } cnt++; } // Check if there was a cycle if(cnt != V) { System.out.println("There exists a cycle in the graph"); return ; } // Print topological order for(int i : topOrder) { System.out.println(i+" "); } System.out.println("tempo de execucao: " + (System.currentTimeMillis()/1000)); }
Desculpe não ter respondido antes. Mas essa semana está sendo punk pra mim. Bom, vamos lá. Tenho um for dentro de um while (custo quadrático). Para saber o custo exato, tem-se que analisar a quantidade de possíveis nodos adjacentes, pois o custo está diretamente ligado a isso ( for(int node : adj[u])). Poderia tomar como n (tamanho de q) e n (tamanho de m), a princípio meu custo seria da ordem O (m.n), mas também seria necessário saber o custo, ou pelo menos a ordem dos métodos usados nesse trecho (poll(), add(obj))
O for começa a ser contado quando i=0 e termina quando a comparação for falsa. A comparação será falsa quando i=mat.length, ou seja, quando i=n. Assim, teremos seu custo 2(n+1). Observe que o custo do for é um a mais que o custo dos comandos que estão dentro dele.
Em um algoritmo qualquer você deve contar as atribuições e as comparações. Assim, o princípio é o mesmo, independente do comando. O for tem os dois (atribuição e comparação) no mesmo comando, por isso seu custo será dobrado. O while só possui a comparação, pois se houver atribuição, ela estará no seu corpo e será contado na linha em que aparecer. Espero que tenha esclarecido
Caro Lairo, observe que os algoritmos são ligeiramente diferentes, embora façam a mesma coisa, ou seja, procurar o maior elemento de um vetor. Este algoritmo é um pouco mais eficiente que aquele. Então vamos lá: No algoritmo desse vídeo, temos que o segundo for é : for (j=1; j
Prece uma coisa simples, mas a dica do maior menos o menor +1 esta me ajudando muito
Obrigado professora
Mt bom. Obrigado!
Faz mais vídeos por favor! Sua explicação em 13 minutos fez eu entender mais do que 1 mês com o meu professor, e se duvidar vai acabar o semestre e eu não vou entender nem 1 virgula com a explicação dele.
@cinthia vendo em 2020. bastante util
Shoooow de bola! Deus vos abençoe!!!
Muito obrigado Cinthia Caliari !! você merece o meu like e a minha inscrição
Ah se todos fossem iguais a você, que maravilha aprender... Obrigado professora!
Excelente explicação!!!!!
Parabéns pela didática de ensino. Excelente aula! Obrigada!
Explicação maravilhosa!!! Obrigada!
Oi professora! Gostei muito da aula :). Tenho uma dúvida, no exemplo 2 no primeiro for ficou 2(n+1) mas não deveria ser 2n... não entendi. Grata pela atenção.
Bom dia. De zero até n, fazendo o maior menos o menor mais um,.termos n-0+1 = n+1
Maravilha de explicação !
Fé no pai que aquela aprovação sai!!!
E quando o método é recursivo, como faço?
No If a condição de parada é se a posição for par correto, Custo = 1? Por fazer uma comparação uma vez. No Else não sei como medir o custo. Me ajuda por favor.
int q1(inf[ ] vet, obg pos){
If(pos== vet.length/2) return vet[ pos];
Else return (vet[pos] + vet[ver.lenght-1-pos] + q1(vet, pos+1));
}
Em qual livro encontro esse assunto?
Estou procurando uma bibliografia para ter mais referencia.
Muito obrigada...
Obrigado!!!!!
Obrigadaaa!
Duvida Urgente!!!
Se abaixo de um if tiver um retorno o custo desta operação abaixo será 1 no pior caso,por exemplo:
for(...) --> custo 2(n+1)
if(..) --> custo n
return true; --> custo no pior caso = 1 ou N
Se dentro do if tiver um retorno, o fato dele entrar no if na primeira vez será considerado o melhor caso, e aí
for(...) --> custo 2
if(..) --> custo 1
return true; --> custo 1
O pior caso é ele nunca entrar no if
for(...) --> custo 2(n+1)
if(..) --> custo n
return true; --> 0
Excelente Aula, ajudou muito. Abrigado... E quando temos esse caso:
while(!q.isEmpty()) # n
{
int u=q.poll();
topOrder.add(u);
for(int node : adj[u])
{
if(--indegree[node] == 0)
q.add(node);
}
cnt++; # 1
}
Esse trecho de algoritmo é quadrático, pois temos um comando de repetição dentro de outro (for dentro de while). Mas para fazer o cálculo exato, é necessário saber o número mínimo e máximo de vértices adjacentes de cada nodo.
é mais ou menos assim o algoritmo que tenho:
int V;// No. of vertices
//An Array of List which contains
//references to the Adjacency List of
//each vertex
List adj[];
long tempoInicial = System.currentTimeMillis();
public Graph(int V)// Constructor
{
this.V = V;
adj = new ArrayList[V];
for(int i = 0; i < V; i++)
adj[i]=new ArrayList();
}
// function to add an edge to graph
public void addEdge(int u,int v)
{
adj[u].add(v);
}
// prints a Topological Sort of the complete graph
public void topologicalSort()
{
// Create a array to store indegrees of all
// vertices. Initialize all indegrees as 0.
int indegree[] = new int[V];
// Traverse adjacency lists to fill indegrees of
// vertices. This step takes O(V+E) time
for(int i = 0; i < V; i++)
{
ArrayList temp = (ArrayList) adj[i];
for(int node : temp)
{
indegree[node]++;
}
}
// Create a queue and enqueue all vertices with
// indegree 0
Queue q = new LinkedList();
for(int i = 0;i < V; i++)
{
if(indegree[i]==0)
q.add(i);
}
// Initialize count of visited vertices
int cnt = 0;
// Create a vector to store result (A topological
// ordering of the vertices)
Vector topOrder=new Vector();
while(!q.isEmpty())
{
// Extract front of queue (or perform dequeue)
// and add it to topological order
int u=q.poll();
topOrder.add(u);
// Iterate through all its neighbouring nodes
// of dequeued node u and decrease their in-degree
// by 1
for(int node : adj[u])
{
// If in-degree becomes zero, add it to queue
if(--indegree[node] == 0)
q.add(node);
}
cnt++;
}
// Check if there was a cycle
if(cnt != V)
{
System.out.println("There exists a cycle in the graph");
return ;
}
// Print topological order
for(int i : topOrder)
{
System.out.println(i+" ");
}
System.out.println("tempo de execucao: " + (System.currentTimeMillis()/1000));
}
Desculpe não ter respondido antes. Mas essa semana está sendo punk pra mim. Bom, vamos lá. Tenho um for dentro de um while (custo quadrático). Para saber o custo exato, tem-se que analisar a quantidade de possíveis nodos adjacentes, pois o custo está diretamente ligado a isso ( for(int node : adj[u])). Poderia tomar como n (tamanho de q) e n (tamanho de m), a princípio meu custo seria da ordem O (m.n), mas também seria necessário saber o custo, ou pelo menos a ordem dos métodos usados nesse trecho (poll(), add(obj))
Muito obrigado!
O custo do for do exemplo 2 não é 2n?
O for começa a ser contado quando i=0 e termina quando a comparação for falsa. A comparação será falsa quando i=mat.length, ou seja, quando i=n. Assim, teremos seu custo 2(n+1).
Observe que o custo do for é um a mais que o custo dos comandos que estão dentro dele.
Hum entendi muito obrigado.
Cadê a aula 2 ??
O link não leva a nenhum video
th-cam.com/video/4pE4myLN7PE/w-d-xo.html
Obrigado mas ainda tenho duvidas com while e da mesma forma que o for ?
Em um algoritmo qualquer você deve contar as atribuições e as comparações. Assim, o princípio é o mesmo, independente do comando.
O for tem os dois (atribuição e comparação) no mesmo comando, por isso seu custo será dobrado. O while só possui a comparação, pois se houver atribuição, ela estará no seu corpo e será contado na linha em que aparecer.
Espero que tenha esclarecido
Fiquei em dúvida agora, pois vi um outro vídeo que deu outro valor no mesmo código: th-cam.com/video/4pE4myLN7PE/w-d-xo.html
Caro Lairo, observe que os algoritmos são ligeiramente diferentes, embora façam a mesma coisa, ou seja, procurar o maior elemento de um vetor. Este algoritmo é um pouco mais eficiente que aquele.
Então vamos lá:
No algoritmo desse vídeo, temos que o segundo for é : for (j=1; j