Calculo de Custo - Aula 1

[@ItachiUchiha-fd5cs]

Prece uma coisa simples, mas a dica do maior menos o menor +1 esta me ajudando muito Obrigado professora

[@nathaliacarnevalli]

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.

[@CinthiaCaliari]

Bom dia. De zero até n, fazendo o maior menos o menor mais um,.termos n-0+1 = n+1

[@jeftefariamatamba6030]

@cinthia vendo em 2020. bastante util

[@mirellas.4243]

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)); }

[@robertdccaetano]

Shoooow de bola! Deus vos abençoe!!!

[@edvandesousasilva]

Em qual livro encontro esse assunto? Estou procurando uma bibliografia para ter mais referencia.

[@mynameispaulocesar]

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.

[@teocritoheleno4171]

Ah se todos fossem iguais a você, que maravilha aprender... Obrigado professora!

[@edilsonfranca3222]

Muito obrigado Cinthia Caliari !! você merece o meu like e a minha inscrição

[@italo1398]

Maravilha de explicação !

[@abner9829]

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

[@CinthiaCaliari]

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

[@andrealuiza9674]

Parabéns pela didática de ensino. Excelente aula! Obrigada!

[@jhonataamboni8259]

Mt bom. Obrigado!

[@weronicas.santos6700]

Explicação maravilhosa!!! Obrigada!

[@mirellas.4243]

Excelente explicação!!!!!

[@MarcosOliveira1]

Fé no pai que aquela aprovação sai!!!

[@zuenirclaudio4941]

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 }

[@CinthiaCaliari]

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.

[@zuenirclaudio4941]

é 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)); }

[@CinthiaCaliari]

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))

[@paulamyrianlimapedroso1272]

Muito obrigada...

[@thiagonunes2751]

Obrigado!!!!!

[@lairochampoudry9071]

Fiquei em dúvida agora, pois vi um outro vídeo que deu outro valor no mesmo código: kzbin.info/www/bejne/aqGoZaCvgbNqhqc

[@CinthiaCaliari]

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

[@amandaazevedo5902]

Obrigadaaa!

[@Luc4sm13]

Muito obrigado!

[@JuniorAlves-hd5td]

Cadê a aula 2 ??

[@JuniorAlves-hd5td]

O link não leva a nenhum video

[@CinthiaCaliari]

kzbin.info/www/bejne/aqGoZaCvgbNqhqc

[@JuniorAlves-hd5td]

Obrigado mas ainda tenho duvidas com while e da mesma forma que o for ?

[@CinthiaCaliari]

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

[@charlesagra9446]

O custo do for do exemplo 2 não é 2n?

[@CinthiaCaliari]

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.

[@charlesagra9446]

Hum entendi muito obrigado.