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!
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.
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
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)
".....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)
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
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!
+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.
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.
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!
+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
+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
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.
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.
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.
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).
´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
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
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?
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)
+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
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!
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.
Explicação de 11m que me fez entender o que meu professor de Paa não conseguiu ensinar em horas... Nice video!
Ótima aula
Aula muito boa. Meus parabéns.
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
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.
Muito bom, professora ! Explicação ótima. Recomendei o vídeo para colegas de sala!
Foda tua explicação, mais didáticas que vi no youtube, eu compraria tranquilo um curso seu sobre complexidade de algoritmos.
Excelente vídeo!
Aula perfeita, meus parabéns.
Muito boa explicação, excelente didática.
excelente revisão professora, valeu
Muito obrigado pela aula!
Excelente vídeo Professora.
Meu professor não conseguiu ensinar em 2 meses o que tu ensinastes em 2 minutos. Muito obrigado :D
Verdade
Ela é minha PROFESSORA hahahaha
Muito bom professora!
Excelente explicaçao! Obrigado
realmente, que explicação boa de uma coisa complicada. 1milhão de likes obrigado
Professora, permita uma correção. Nos seus vídeos, a senhora afirma que laço for(i=0;i
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)
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
".....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)
"verdade é isso --> i+=1 (mesma coisa que i = i +1)"
então conta como duas instruções (uma soma e uma atribuição)?
Excelente explicação. 😊
Excelente explicação!
Muito bom!
sensacional!
show de aula
Obrigado pela aula! c:
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?
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
é isso mesmo
@@CinthiaCaliari repara q o i comeca com zero
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!
+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.
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
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.
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
Não entendi muito bem porque no primeiro exemplo, no melhor caso, ficou 3n^2
Em qual livro encontro esse assunto?
Estou tentando encontrar uma bibliografia pra eu ter mais referência.
Bom dia
Cormen, T. H et al. Algoritmos : teoria e prática
@@CinthiaCaliari Muito Obrigado!!!
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
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!
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
entendi Cinthia! obrigado
professora, no custo do melhor caso, eu não entendi o 2n²+2n no segundo for, pode me explicar? 4:19
+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
não há um erro em 10:33? soma vai até n-1 e não até n...se possível responder
+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
não seria algo em torno de n*log(n)?
Em nenhum dos exemplos apresentados temos custo n*log(n), mas você está se referindo a qual exemplo?
Não está faltando um colchete fechado no segundo "for", logo após a a primeira "soma"?!
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.
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.
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.
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).
´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
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
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?
desculpa, busca sequencial
Nao consegui encontrar onde deu 7n :/ , meu somente deu 6n
2n+2n/2-n/2+n = (4n+2n-n+2n)/2 = 7n/2
@@CinthiaCaliari vish, entendi não esse 7n aí
@@mynameispaulocesar Tem que tirar o mínimo
sum = 0;
for (i = 0; i < 3; i++)
for (j = 0; j < n; j++)
sum++;
poderia fazer essa?
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)
+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
+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
Que linguagem é essa C ?
Fiz em Java, mas como os dois são muito parecidos, nos seus comando básicos, alguns podem pensar que é C
tendi nada