Calculo de Custo de Algoritmo (quadrático)

[@andreysantos6660]

Com o perdão da palavra, mas que aula do CARALHO! nenhum professor meu jamais me explicou assim, cheios de títulos e etc, mas não conseguem dar uma explicação tão clara e concisa. Ensinar é um dom que honraria nenhuma compra. PARABÉNS!

[@Dudlles]

Boa tarde, não costumo logar para comentar mas desta vez fiz questão, para te parabenizar pela forma clara e dedicada de explicar . Um grande abraço, continue seu excelente trabalho.

[@epilefsotnas4728]

Explicação de 11m que me fez entender o que meu professor de Paa não conseguiu ensinar em horas... Nice video!

Aula muito boa. Meus parabéns.

[@marcielledepaula3373]

Ótima aula

[@leom553]

Muito bom, professora ! Explicação ótima. Recomendei o vídeo para colegas de sala!

[@fsbf1]

Me junto aos colegas comentarista para elogiar a aula, sou mestrando e estou na merda nessa matéria. Vi aqui uma luz de esperança.

[@gtbronks]

Excelente vídeo!

[@fernando2852]

Foda tua explicação, mais didáticas que vi no youtube, eu compraria tranquilo um curso seu sobre complexidade de algoritmos.

[@Zinidxx]

Caralho, vtnc, pqp vc é maravilhosa. Cara, que forma fácil de explicar didática. Amei, muito obrigado. Alias assisti até outros vídeos seu. Por favor, substitua meu professor

[@F4n74.]

Aula perfeita, meus parabéns.

[@flaviodeassis9359]

Muito boa explicação, excelente didática.

[@rafaeldsouza]

excelente revisão professora, valeu

[@LukasHsLima]

Muito obrigado pela aula!

[@Anaquerziada]

Excelente vídeo Professora.

[@VitorOliveira-by9iw]

Excelente explicaçao! Obrigado

[@fellippaak]

Muito bom professora!

[@lllalazinha]

Excelente explicação. 😊

[@maahbtc]

Meu professor não conseguiu ensinar em 2 meses o que tu ensinastes em 2 minutos. Muito obrigado :D

[@yah_2589]

Verdade

[@MarcosOliveira1]

Ela é minha PROFESSORA hahahaha

[@edsonmottac]

Excelente explicação!

[@fernandosantos885]

realmente, que explicação boa de uma coisa complicada. 1milhão de likes obrigado

[@wandermm]

Professora, permita uma correção. Nos seus vídeos, a senhora afirma que laço for(i=0;i

[@CinthiaCaliari]

Meu caro, mas é exatamente isso que eu falo a partir de 0:58s: "O for vai ser rodado n+1 vezes (a linha do for e não seus comandos internos, que serão rodados n vezes apenas). O custo dele é dobrado pq toda vez que a linha do for é executada, ou ele executa i=0 e a comparação (no caso da primeira vez) ou ele executa i++ e a comparação, no caso das outras n vezes. Então teremos um total de 1.2+n.2 = 2+2n = 2(1+n) = 2(n+1). Isso quer dizer que sendo rodado n+1 vez com custo 2 a cada vez que rodar, tem-se um total de 2(n+1)

[@makeemoneey]

Cinthia Caliari, na primeira vez que rodar o laço, é executado apenas duas instruções, a atribuição "i=0" e a comparação "i

[@gabrielnilo6101]

".....o "i++", que na verdade é "i = i + 1" (2 instruções)....... " na verdade o i++ tem valor de 1. verdade é isso --> i+=1 (mesma coisa que i = i +1)

[@makeemoneey]

"verdade é isso --> i+=1 (mesma coisa que i = i +1)" então conta como duas instruções (uma soma e uma atribuição)?

[@tatocavalcante8070]

show de aula

[@LonelyTroubadour]

Obrigado pela aula! c:

[@beanascimento5456]

sensacional!

[@igormatheus4516]

Muito bom!

[@ramonrodrigues7301]

Que inveja, queria que meu professor(a) de Técnicas e análise de algoritmos tivesse pelo menos 10% da sua didatica professora, parabéns

[@franciscos.f9474]

Não entendi muito bem porque no primeiro exemplo, no melhor caso, ficou 3n^2

[@jonnathanlopes1195]

Outra dúvida, por que todo for é multiplicado por 2, no livro do shaffer não é analisado assim! Abraço posta mais videos de resolução desses exercícios!

[@CinthiaCaliari]

+Jonnathan Lopes Aqui eu estou analisando o custo de todas as comparações e todas as atribuições. Como no "for" tem sempre uma comparação e uma atribuição, é necessário multiplicar por 2.

[@marigoj]

O for vai parar quando MENOR QUE N = mat.length, e não MENOR ou IGUAL que... então será executado N vezes e não N+1, ou estou enganado?

[@CinthiaCaliari]

Meu caro, o for vai PARAR quando a condição for FALSA e isso acontecerá quando i=mat.length. Portanto, a linha do for e só ela, será executada n+1 vezes

[@anacletomachava5779]

é isso mesmo

[@anacletomachava5779]

@@CinthiaCaliari repara q o i comeca com zero

[@edvandesousasilva]

Em qual livro encontro esse assunto? Estou tentando encontrar uma bibliografia pra eu ter mais referência.

[@CinthiaCaliari]

Bom dia Cormen, T. H et al. Algoritmos : teoria e prática

[@edvandesousasilva]

@@CinthiaCaliari Muito Obrigado!!!

[@matheusvianna3067]

Poh Vey único PS é que você vai calculando os valores só apostando não explica da onde tá vindo as coisas pra fazer a fórmula final

[@matheusviniciusandrade2733]

A linha que vc chamou de (II) é executada (n^2 -2)/2 por conta do for mais interno, porém vc não deveria multiplicar por n , já que essa linha será executada para cada uma das n vezes que o for mais externo roda ?? Porque ao que me parece vc só contabilizou as vezes que essa linha vai rodar levando em conta só o for mais interno.

[@CinthiaCaliari]

a expressão que deu origem à (n^2-n)/2 foi (n-1).n/2, logo, observe que o n foi multiplicado por (n-1). Então, não está faltando nada

[@mrjmrezende]

Olá professora,Não interfere no conceito da explicação, que continua excelente, mas acredito que no segundo exemplo, no parâmetro, está faltando mais um conjunto de colchetes, visto que a matriz tem duas dimensões.

[@JeffJulianZone]

Olá professora td bem? Obrigado pelo vídeo ajudou bastante! Estou com dúvida no segundo exemplo. Não entendi porque na sua tabela, o elemento soma você inicia com 0 vezes. No meu ver a soma entra quando mat[0][0] é chamado. Não entendi porque não contou. Obrigado!

[@CinthiaCaliari]

Bom dia Jeff, soma inicia com zero pq na primeira vez, i=0 (entra no primeiro for) j=0 (não entra no segundo for, pq j tem que ser

[@JeffJulianZone]

entendi Cinthia! obrigado

[@higorcardoso1055]

Não está faltando um colchete fechado no segundo "for", logo após a a primeira "soma"?!

[@CinthiaCaliari]

No segundo exemplo, a primeira soma está dentro do segundo for e a segunda soma dentro do primeiro for. Como o segundo for só tem um comando dentro dele (a primeira soma), ele não precisa ter chaves.

[@Evanheads]

professora, no custo do melhor caso, eu não entendi o 2n²+2n no segundo for, pode me explicar? 4:19

[@CinthiaCaliari]

+Evandro Depiante Ele entre no primeiro for n vezes (e inicia o segundo for). Roda o segundo for de 0 até n, ou seja n+1 vezes, para cada vez que iniciar o for. Portanto ele rodará n.(n+1). mas, como o for tem comparação e atribuição, ou seja,, duas operações relevantes, é necessário multiplicar por dois. Assim, seu custo será n.(n+1).2 = 2n^2+2n

[@pedrocamposcavalcanti3080]

não seria algo em torno de n*log(n)?

[@CinthiaCaliari]

Em nenhum dos exemplos apresentados temos custo n*log(n), mas você está se referindo a qual exemplo?

[@jonnathanlopes1195]

não há um erro em 10:33? soma vai até n-1 e não até n...se possível responder

[@CinthiaCaliari]

+Jonnathan Lopes Caro Jonnathan Em SOMA, você tem uma PA que pode ser a1=0, an = n-1, tendo n termos, portanto a soma é (a1+an).ntermos/2=(0+n-1).n/2, que foi o que fiz ou então a1=1, an=n-1, tendo n-1 termos, portanto a soma é (1+n-1).(n-1)/2, que dá no mesmo

[@robertdccaetano]

Nao consegui encontrar onde deu 7n :/ , meu somente deu 6n

[@CinthiaCaliari]

2n+2n/2-n/2+n = (4n+2n-n+2n)/2 = 7n/2

[@mynameispaulocesar]

@@CinthiaCaliari vish, entendi não esse 7n aí

[@CinthiaCaliari]

@@mynameispaulocesar Tem que tirar o mínimo

[@Pain28248]

Se a questão foi analisar passo a passo o algoritmo, faltou mais informações. Primeiro pq o laço for não executa apenas 2n vezes. Primeiro pq mesmo a matriz estando vazia, pelo menos o primeiro laço vai realizar duas instruções que é a atribuição e a comparação que daria 2 + 2n(que seria executado a cada iteração). Sobre o lance do iterar n + 1 vezes, eu discordo até porque se formos considerar o valor inicial das variáveis de iteração do seu for: i = 0 fazendo i iterar a um limite n, veremos que ele vai iterar n - 1 vezes.

[@CinthiaCaliari]

Primeiro) Se a matriz estiver vazia ele fará; 2 vezes sim, o for de fora, e eu não omiti isso, talvez você não tenha percebido que 2(n+1) = 2n + 2 (aplicação direta da propriedade distributiva da matemática), assim, se n=0, temos 2(0+1) = 2.0+2 = 2. Segundo) veremos que ??? - não houve conclusão da frase, mas responderei assim mesmo: Se i começa com zero (0) e termina em n (termina quando a comparação for falsa), temos n+1 vezes (pode contar usando a metodologia que quiser, se estiver matematicamente correta, dará n+1 vezes).

[@Pain28248]

´pode debugar um código qualquer! Vc começa em zero, então o o tamanho do vetor é tam-1. Se o seu vetor tem 10 posições com elementos aleatórios, o pior caso de uma busca sequencial, por exemplo vai ser (n-1), pois com i seu i n. Se considerar que é n + 1, vc estaria buscando uma posição que nao existe e no último elemento do seu vetor seria 9, pois 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.quando o seu i for para 10 a condição será falsa, ou seja, o laço termina, pois 10 não é menor do que 9. Se sua condição de parada do for fosse i

[@CinthiaCaliari]

Continuando o seu raciocínio, se o vetor tem 10 posições (0 a 9), quando o i rodar entre 0 e 9 (ou seja, 10 vezes), ele entra no for e inicia o for de dentro (o do j). Na última vez, ou seja, quando i=9, na saída, i é incrementado de 1, passando a valer 10, e é comparado a mat.length, como o resultado será falso, o for para de ser executado e o comando passa para a linha após o for. Então, ele executou a linha do for (10 vezes - de zero a nove + a última vez com i=10 para que o resultado i

[@Pain28248]

mas a senhora tá considerando o i. Leia direitinho, eu disse que o i chegaria a 10 e quando fosse para condição, ele parava. Mesmo o i sendo incrementado, não se pode provar que são 10 iterações, porque quando o i for 10 laço para e o que está dentro não é executado.Por exemplo se eu faço uma busca binária em um vetor de 10 posições sendo que o numero encontrado está na ultima posição eu tenho que afirmar que o número de passos do meu algoritmo é 10 + 1 se o a ultima de iteração de encontro do elemento encerra o algoritmo?

[@Pain28248]

desculpa, busca sequencial

[@jonnathanlopes1195]

sum = 0; for (i = 0; i < 3; i++) for (j = 0; j < n; j++) sum++; poderia fazer essa?

[@jonnathanlopes1195]

pelo seu vídeo minha análise seria : Linha 1 - Custo C1Linha 2 - Custo C2 = 4 unidades.Linha 3- For interno, 2x3(n+1) (essa linha será iniciada 3 vezes, pois quando a linha 2 se torna falsa já não entra no for interno, além disso tem custo dobrado, pois há uma atribuição e uma comparação toda vez que é executada). Linha 4 - C3 T(n)= C1+C2+6n+6+C3 = 6n+C (chamando todas as constantes de = Θ(n)

[@CinthiaCaliari]

+Jonnathan Lopes Linha 1 = 1 Linha 2 - 4x2=8 Linha 3 - 3x2(n+1) (custo dobrado pq tem uma comparação e uma atribuição) Linha 4 - 3xn C(n) = 9n+15

[@jonnathanlopes1195]

+Cinthia Caliari eu não teria que colocar no for interno 3x2(n+1), pois ele será executado 3 vezes.... Muito Obrigado pela atenção, estou tendo dificuldade nessa disciplina no mestrado!Abraço

[@paulozera_enbassadaoa3767]

Que linguagem é essa C ?

[@CinthiaCaliari]

Fiz em Java, mas como os dois são muito parecidos, nos seus comando básicos, alguns podem pensar que é C

[@GustavoHenrique-xg4ey]

tendi nada