COMPLEXIDADE de ALGORITMOS I - Noção INTUITIVA
Vložit
- čas přidán 16. 07. 2024
- Neste vídeo, introduzimos conceitos fundamentais na análise da eficiência de soluções computacionais a partir da intuição sobre complexidade de algoritmos. Esses conceitos serão a base para entendermos como profissionais de computação analisam a quantidade de recursos demandada por seus programas.
Como explicado no vídeo sobre recursos computacionais ( • Recursos Computacionai... ), nossos programas demandam alguma forma de processamento, isto é capacidade de cálculo, e também memória, espaço de armazenamento. Assim, podemos medir a complexidade de um algoritmo de duas formas: complexidade de tempo e complexidade de espaço.
Nesta primeira parte, buscamos entender o conceito de "operação elementar", que nos ajudará a simplificar o raciocínio acerca das duas formas de complexidade. Na parte II ( • Notação do O Grande - ... ), nós aprenderemos a notação do O grande, a mais utilizada para especificar a complexidade de algoritmos.
** ERRATA 1: O correto seria usar a variável "tamanho" no lugar de "n" na função *inverter_lista*.
*ERRATA 2: Aos 13:25, calcula-se a complexidade de espaço como 3+2N, porém o correto seria 2+2N. Existe uma necessidade de espaço a mais que poderia ser interpretada pela operação de subtração das variáveis "tamanho" e "i", mas esse é um rigor do qual não precisamos para essa tarefa em particular.*
0:00 Introdução e conceito de complexidade
1:36 Programa e Algoritmo
2:24 Análise do algoritmo de inverter uma lista
4:48 Contagem de variáveis e memória
5:40 Contagem de Operações Elementares
8:0X Complexidade de Espaço e Complexidade de Tempo
10:32 Por que a análise de complexidade é importante
14:04 Resumo da aula e conceitos essenciais
* Livro de Algoritmos:
Versão em português
Algoritmos - amzn.to/2LbAAQa
Versão em inglês
Introduction to Algorithms - amzn.to/2xCwl7l
📚 Livro para estudar Bancos de Dados - amzn.to/3Hjjusc
📚 Livros recomendados de Data Science: amzn.to/2XZyxUr
📚 Livros de Algoritmos e Estruturas de Dados: amzn.to/3d5wK4m
SetUp - Equipamentos: amzn.to/37Cg3N2
🟣 Canal na Twitch para lives: / pgdinamica
🟦 Canal do Telegram para receber todos os vídeos: t.me/pgdinamica
🥰 Se você gosta do nosso trabalho e acha relevante a nossa atuação no CZcams, considere nos apoiar se tornando membro do canal: czcams.com/users/programacaodi...
✉️ E-mails:
- Propostas comerciais: pgdinamica@brunch.ag
- Demais assuntos: contato@programacaodinamica.com.br
👩🏾💻👨🏾💻 Confira mais conteúdo em nosso blog: / programacaodinamica
TikTok: @pgdinamica
📸 Nos siga no Instagram: / pgdinamica
📸 @kizzy_terra @hallpaz
🐦 Nos siga no Twitter: / pgdinamica
🐦 @kizzy_terra @hallpaz
* Curta a Programação Dinâmica no facebook: pgdinamica
* Nosso repositório no Github: github.com/programacaodinamica
* Confira os artigos no Python Café: pythoncafe.com.br
Saudações a todos. Por gentileza, o que é esse n ai no código? Seria a variável tamanho? Um grande abraço.
É, sim, bem observado Fábio, obrigado! O correto seria usar a variável "tamanho" no lugar de "n" na função *inverter_lista*.
@@pgdinamica Fiquei me perguntando isso com a variável "i", se possível pra facilitar pra gente quando for ler se puder criar nomes mais claros, facilita pelo menos pra mim. Eu refaço os exercicios e acabo me perdendo no contexto dos nomes das variáveis pq não fica claro o que ela faz :) ai ja me ajuda aqui brigadinhu. Parabéns pelo canal, ajuda mtooooo
@@pgdinamica mas de qualquer forma, canal de vocês é sensacional. Obrigada por compartilhar e ensinar, que farei minha parte aqui do lado, compartilhando e divulgando
Meu caro... Nunca comento no CZcams, mas você merece. Parabéns pelo trabalho, sua didática é ótima. Um abraço e muito obrigado.
Obrigado pelo reconhecimento! :)
Cara, sua didática é incrível, em todos os seus videos o nível de qualidade é extremamente bom, o canal é execelente
muito bom, bastante claro!
Seus vídeos são ótimos!!! Muito obrigada!!!
Muito bom! Parabéns! Conteúdo incrível!
Assistido✔️
Que diferença uma boa didática faz, já estudei um pouco sobre complexidade, mas você fez eu entender melhor que outros vídeos que assisti. Bimestre que vem na faculdade vou ter algoritmos e logica de programação 1 e 2 então seus vídeos já estão me preparando.
Muito bom!
Como assim eu não conhecia esse canal antes ??????? AMEI
Parabéns ótimo trabalho
Canal foda , continua .
excelente vídeo
OBRIGADO AMIGO VC SALVOU MEU BIMESTRE
Sensacional os seus vídeos !
Muito obrigado, Aline! Bons estudos!
Parabéns aos integrantes do canal, qualidade excelente e impecável dos vídeos. A explicação dessa aula ficou top demais!!! Muito bom mesmo. Parabéns.
Valeu! Muito obrigado 😊
Para quem for tentar fazer as funções mude onde for n-i por n-1-i pois o range sempre vai até o antecessor de n. (n é o tamanho da lista).
Ótima aula, parabéns.
Muito bem observado, Rogerio, obrigado! Dessa vez, como não testamos, esses erros me passaram despercebidos Tanto os índices, como o nome da variável. Abração!
obrigado
Muito bom vídeo!
Obrigado pelo apoio, Samuel!
Muito obrigado pelo vídeo...
Nós que agradecemos! Bons estudos!
Tão didático! Obrigada =)
De nada! 🖖🏾
Muito obrigado por compartilhar seu conhecimento conosco, os videos sao muito bons
Valeu, Patrick!
Meus algoritmos matemáticos são um complexo de todas as áreas diferentes da disciplina. Álgebra, geometria, teoria dos números, números romanos, combinatória e teoria dos grafos num único fenômeno matemático.
Muito bom esse vídeo! Me ajudou a entender bem como funciona esse conceito.
Que ótimo! Bons estudos 😉
Ba cara, parabéns, muito bom o vídeo.
Obrigado!
Gostei muito do estilo do vídeo e da explicação. Ajudou bastante.
Obrigado, Robson! Bom saber que te ajudou!
MANO QUE CONTEUDO INCRIVEL, MARAVILHOSO, VC É INCRIVEl. Obrigado pelo conteudo!!!
🥰🥰🥰
Muito obrigado pelo conteúdo! parabéns
De nada! 😁
Sua didática é incrível, to adorando a playlist!
Muito obrigado! Bons estudos :)
CANAL INCRÍVEL...
Agradeço e fico feliz com o comentário, frances Guedal :)
ÓTIMA explicação.
Muito obrigado, Nayara!
Vídeo show! Inscrito + like!
Muito obrigado, Jhow!
Ajudou muito!! Valeu!
De nada!
Cara muito legal seu vídeo, obrigado!!
Valeu! 😁
Vou ter Algoritmos e Estruturas de Dados nesse período e a matéria de Complexidade de Algoritmos é a primeira da ementa, aí vim ver como é, excelente vídeo amigo, obrigado!
Valeu, bons estudos!
Vídeo excelente, ótima explicação!
Muito obrigado!
Embora eu já tenha uma boa noção do assunto é sempre bom ouvir um pouco mais. Parabéns pela didática.
Também penso assim, obrigado!
cara desejo todo sucesso profissional pra você, você transmite uma vibe muito boa enquanto explica algo, só senti algo assim antes com o felipe deschamps
Muito obrigado, Antony! 🥰
Obrigado pelo trampo
De nada!
Muito bom
Mas é um arraso!!! Cada aula , seja ela qual for , é um mar de novas descobertas ou de aperfeicoamento. Excelente como sempre!
Muitíssimo obrigado!
Boa explicação, curti o vídeo.
Obrigado!
Muito bom!! Parabéns pelo conteúdo.
Muito obrigado 😁
Cara tu explica muito bem! Se garantiu, parabéns!
Valeu, obrigado! 😊
Cara obrigada.parabés
De nada! ;)
Voce é muito brabo mano!
Valeu!
Excelente didática. Parabéns pelo vídeo
Muito obrigado! 😊
obrigado pelo conteúdo, me ajudou a entender mais sobre complexidade de algoritmos
Que ótimo, bons estudos!
muito bom!
Valeu! 😊
Maratonando para aprender mais sobre algoritmos
Top! Bons estudos 🙌🏾
👏🏻👏🏻👏🏻👏🏻👏🏻👏🏻👏🏻👏🏻 Excelente didática !!! Já recebeu minha curtida e inscrição o canal.
Muito obrigado 😃
Ótimo vídeo
Muito obrigado!
Cara, muito bom
Valeu 😊
Mutcho bão! Parabéns!
hahah valeeeu!
Muito bom o video, parabéns pelo trabalho
Valeu!
Me inscrevi hj no canal, primeiro vídeo que vi já fiquei doido:)
Caramba que massa pow, da nem pra acreditar que tu fez um trabalho desses, parabéns pelos vídeos mano, tudo de bom pra vcs, vou zerar essa playList igual um viciado haha
Esse assunto é muito divertido
Seja bem vindo! Bons estudos!
Um dos melhores professores que já tive me salvando no último período da faculdade kkkkkkkkk. Obrigado Hallison!!
🥰
Show!
🤩
Por enquanto estou entendendo, top
Bons estudos!
Obrigado cara. Está clareando. abraços;
Valeu, bons estudos!
Obrigade por salvar minha vida, amei !!
De nada! Bons estudos 🙌🏾
Cara, tu é muito bom explicando. Parabéns!
Obrigado! Bons estudos 😉
Bacana demais! Me salvando na faculdade. Muito obrigada!
De nada! Bons estudos!
Ótimo vídeo cara. 👏👏👏📝📈📚 Salvando disciplina do curso de engenharia da computação. Deus te abençoe. Tmj
Valeu 😊 sucesso nos estudos!
Quanto custo tem o seu algoritmo?
•Contagem de variáveis e memória -> espaço
•Contagem de passos elementares -> tempo
▪︎Passos elementares -> Não escondem um outro algoritmo. N° de passos constantes
Como a complexidade muda com o / em função do o tamanho da entrada?
Esse vídeo me ajudou a entender a complexidade de um algoritmo, detalhe ÚNICO CANAL, obrigado e faz mais vídeos por favor rs mais um inscrito
Fico feliz em saber Edd! Também escuto metal 🤘🏾
@@pgdinamica
Metal é bom pra programar as vezes kk
Parabéns pelo canal e obrigado pelo conteúdo que você apresenta no seu canal, tem me ajudado muito
show
Vc tá salvando meu semestre,cara
🙌🏾🙌🏾
parabens. gostei muito do seu cabelo afro-samurai!
Valeu, mano!
Você explica bem dms, me ajudando mt na minha prova especial kakaka, obj
Fala Vitor! Que bom que você gostou! Estamos fazendo umas modificações bacanas no canal para deixá-lo ainda melhor. Quando puder, dá uma conferida nos conteúdos novos 😉
fala bem. parabens pelo conteudo
Muito obrigado!
@@pgdinamica cara,
pq vc nao faz uma serie, fazendo aqueles desafios do hackerrank ou do codiility ia ser bacana!!!
10:15 a partir daqui tudo o que ele falar faz parte da string
11:48 vale a pena assistir as aulas de matemática elementar, bati o olho na função de primeiro grau e fez completo sentido.
Que ótimo!
Puts que canal tezao, ja vou recomendar pra todos os meus amigos. Valeu pelo conteudo cara show de bola
Que alegria! 😊
👏👏👏 didática ótima
Muito obrigado!
Ótima explicação! Tem alguma referência de livro para recomendar?
Comecei o Estrutura de Dados e Seus Algoritmos hoje por indicação do Hallison "do futuro" (em relação a essa postagem) e, após buscar no google conteúdos de fixação do capítulo 1, vim parar no Programação Dinâmica novamente que usa o primeiro exemplo do livro em questão. hehehe
hahaha, "o bom filho, à casa torna" 😂
Valeu, Felipe!
Que vídeo excelente amigo, se você não for professor de universidade eu sugiro que seja, porque sua didática é ótima!
Muito obrigado! Dei aula por dois anos em uma faculdade, parei no começo do ano por conta do doutorado :)
@@pgdinamica ah entendi, às vezes precisamos focar em algo maior e abrir mão de algumas coisas, isso aí! Mas depois de conquistar o título, seria gratificante para um aluno de graduação ter um professor com desenvoltura na didática como vc tem. Eu um dia quero trilhar este caminho, e você já é uma inspiração, abraços!
no alto dos meus 35 anos ta bravo aprender esse trem..kk
entender ja entendi os conceitos...mas implementar para resolver problemas ate simples,ta osso
30 é o novo 20!
caraca.. mesma idade mesmo problema... será q o cerebro buga depois dos 30??
Adorei o vídeo! Meus parabéns pela didática. Uma coisa que eu fiquei em dúvida, mas que o vídeo me sugeriu foi o seguinte: existe um certo equilíbrio entre as complexidades de tempo e de espaço? Quero dizer, sempre que eu conseguir diminuir uma eu terei aumentado a outra?
Obrigado, Frederico! "existe um certo equilíbrio entre as complexidades de tempo e de espaço?" SIM!
*Sempre* é uma palavra muito forte, porque pode ser que a solução em análise não seja a mais otimizada, por exemplo. Mas é possível afirmar que geralmente existe, sim, uma troca entre esses dois recursos. Eu fiz um vídeo específico sobre isso: czcams.com/video/TT8rRUjvzbM/video.html infelizmente, o áudio não está tão bom :/ mas devo voltar a falar disso novamente.
Devo começar por complexidade de algoritmos ou por estrutura de dados ? grande abraço.
Assiste os dois vídeos de complexidade e depois segue pra estruturas de dados ✌🏾. É importante entender a complexidade de buscar, inserir e remover elementos de uma estrutura de dados.
Fiquei com uma duvida tentando executar as funcoes aqui, na funcao 1, como retornar a lista invertida?
para complexidade N:
def invLista(lista):
return lista[::-1]
Fala, MH, blz?
Ambos os algoritmos são O(N), pois 4 + 3N = O(N).
A alternativa que você apresenta reduz as constantes usadas na complexidade de processamento e aumenta as constantes da complexidade de memória, pois o resultado é gerado em um novo espaço de memória, você mantém a lista original e a invertida.
O trade-off ("troca") entre memória e processamento é um "dilema" comum da computação. Tem um vídeo aqui no canal sobre isso.
[]s
Na função "inverter_lista2()" você calculou a complexidade de espaço como sendo igual a " 3 + 2N ". Mas não seria " 2 + 2N " ? Eu não entendi direito de onde foi tirado o 3.
Você está correto, Bruno são apenas 2 mesmo (2 + 2N) por conta das variáveis " tamanho" e "i". Vou adicionar esta nota à descrição do vídeo, obrigado!
Note que raramente você vai precisar desse valor exato, pois na notação do O-grande, o mais importante é identificar como ocorre o crescimento da função.
@@pgdinamica Vou assistir o vídeo sobre a notação do O-Grande.
corrigindo as linhas 9 e 10 da função:
linha 9 ----> lista[i] = lista[(tamanho - 1) - i]
linha 10 ---> lista[(tamanho - 1) - i] = aux
da forma como se encontra no vídeo, o laço tentará acessar uma posição da lista que não existe (em outras palavras, uma posição que excede a última posição da lista), ocasionando um erro de IndexError. Abraços!
Me ganhou na string hehehe
Boa tarde.
Excelente vídeo!! Você recomenda alguma literatura para aprofundar esses conhecimentos? Obrigado!
O mais completo é o livro "Algoritmos" do Cormen (um livro grosso, capa branca). Acabo de redigir um artigo no Medium sobre o assunto, tem indicações de outros livros e materiais que podem te interessar: medium.com/programacaodinamica/o-caminho-dos-algoritmos-6637282ce061
Vlw!
@@pgdinamica muito obrigado pela ajuda. Li o artigo e achei topissimo!!! Obrigado mais uma vez.
@@josehumbertonunes7441 #tmj
e quando temos dois FOR dentro de uma mesma função....sem estar aninhado ?
pois quando o FOR está aninhado eu ja aprendi que fica O(n^2). e quando não está ?
Oi, FLAVIO 2, nesse caso, a complexidade continua sendo O(N). Quando você adiciona outros FOR não aninhados, o efeito produzido é um aumento no tamanho da constante que multiplica o N, então para a notação do O grande, continua sendo O(N).
Se dentro de um FOR você faz 3 operações elementares e dentro de outro FOR não aninhado, faz 5, por exemplo, ao somar o custo de todas as operações você terá 8*N. (3*N + 5*N), o que acaba virando O(N).
Boa noite. Fiquei com um pouco de dúvida na função inverter_lista2, na hora dde calcular a complexidade de tempo, o meu ficou: 2 + 1 * N .
Sendo: 2 = qtd de operações fora do for + 1 = qtd de operações realizadas dentro do for * N = limite de repetições.
Poderia me informar por favor se eu fiz algo de errado?
acho que ele inverteu as grandezas, também percebi isso
De onde vem o valor de n no primeiro algoritmo?
Opa! "O correto seria usar a variável "tamanho" no lugar de "n" na função *inverter_lista*."
tamanho não deveria ser = len(lista) - 1 ao inver de apenas len(lista)?
Boa observação, mas se ajustar a variável *tamanho*, será necessário arredondar o *limite* para cima. Outra opção é deixar *tamanho* como está e adicionar -1 dentro dos colchetes.
vai toma no cu vi nem 8 minutos e tive que parar pra comentar, bom pra caralho!
Meu caro, você tem certeza que a função inverter_lista realmente inverte uma lista?
pois aqui não funcionou nem a pau
fiz tamanho - 1 já que não existe posição lista[tamanho], pois o python possui posição inicial 0(zero)...
lista = [0,1,2,3,4,5,6,7,8,9]
tamanho = len(lista)
limite = tamanho//2
for i in range(limite):
aux = lista[i]
lista[i] = lista[(tamanho-1)-i]
lista[(tamanho-1)-i] = aux
Opa, que bom que identificou o problema no índice! Como o foco era só análise de complexidade, não testei a função à época, então esse problema de índice passou. Nos algoritmos que se seguem, não temos esse problema 🤙🏾
mais da onde veio esse N na linha 9?
é pq a lista pode ter n elementos