Big O Notation (Descubra Agora se Seus Algoritmos São Eficientes) // Dicionário do Programador

e contextualizando brigou não tem chão ou simplesmente beagle é uma anotação no campo da matemática que avalia o comportamento limite de uma função em relação aos valores dos argumentos utilizados chamamos esse campo de análise assintótica de algoritmos e é muito utilizado na computação principalmente na área de algoritmos justamente para calcular a escala habilidade de um código quando os parâmetros tendem a ter um valor específico ou infinito ficou confuso cama que eu te entendo mas a gente vai desvendar isso aqui agora nesse vídeo Então se prepara para entender de vez o que é o pneu e

[Música] A Essência primeira vez que você vê dois programadores de jaleco Então deixa eu nos apresentar eu sou o Gabriel Eu só ganhei essa estamos aqui semanalmente desde 2016 desvendando a sopa de letrinhas que é esse mundo incrível da programação as 2 exames jalecos pois nós somos aí fãs de longa data do mundo de Beakman essa é a nossa singela homenagem a um programa que nos ensinou muito sobre Ciência ela nossa infância com essa mesma pegada estamos aqui para desvendar os principais termos utilizados por nós programadores nesse vídeo não vai ser diferente vamos falar de

algo que está no campo da matemática e também da Computação Big ou se você já pode ficou alguma vez uma função que travou seu computador então você vai gostar de saber o que é isso que estamos aqui do escritório para te contar que nós trouxemos para esse vídeo nossa super parceira roxinha que ao invés de trazer a complexidade de alguns algoritmos que vamos estudar aqui nesse vídeo Ela traz sem e simplicidade para criação do nosso ambiente Cloud então escuta isso todos os planos de hospedagem cloud da Rússia o nome de domínio e certificado SL completamente

gratuita para todos os clientes além de armazenamento SSD backup diário largura de banda e banco de dados ilimitado para conhecer as outras vantagens de garantir aquele um desconto especial na contratação de qualquer um dos planos é só acessar o link está aqui na descrição longe Já começamos a definir o Big ou mas acho que nós conseguimos simplificar e as um pouco mais ela é uma função matemática aplicada na computação para analisar a complexidade de um algoritmo programadores usa ou anotação vigor para analisar as complexidades de espaço e tempo de um algoritmo essa notação mede o

desempenho do limite superior ela ajuda a identificar como desempenho do seu grito mudar a conforme o tamanho de entrada aliás se engana quem acredita que essa análise é feita utilizando somente a notação big-oh que a propósito vende o micro temos também anotação Ômega e theta Mas relaxa que faremos uma abordagem menos matemática e mais prática do ponto de e ao criar um código escolher o melhor algoritmo e estrutura de dados é Deveras importante a notação big-oh ajuda você a comparar o desempenho de vários algoritmos e Encontraram o correto para o seu tipo de código vejo

um mundo de hoje onde muitos deves acreditam que temos processamento memória e armazenamento em Vêneto ter um código bem escrito para cena pro cenário certo faz toda a diferença em dispositivos como uma câmera fotográfica um stream deck o mesmo um smartphone que tem uma capacidade de chips de processamento temos que programar com atenção constante na capacidade em nos limites de rádio em que estamos lidando as complexidades de espaço e tempo dependem de vários fatores como o hardware subjacente sistema operacional CPU processador e etc no entanto quando analisamos o desempenho do algoritmo nenhum desses fatores é

realmente levar em consideração e o que essa complexidade de espaço e tempo que comentamos antes nada mais é que o tempo gasto pelo algoritmo para serem em função do comprimento da entrada exato da mesma forma a complexidade de espaço de um algoritmo especifica a quantidade total de espaço ou memória ocupada por um algoritmo para ser executado em função do comprimento da entrada vamos analisar aqui com um pouquinho de matemática das funções assimptoticamente não negativas FG dizemos que F está na ordem ordem G escrevemos f = o Gigi existem constantes positivos CN Task FDN é menor

ou igual a c g e n para todo n maior que ele maior é isso tudo aí é conhecido como notação assintótica ou notação de Landau tem um algoritmo executa um cálculo em cada e tem dentro de uma rede tamanho n esse algoritmo é executado em tempo o DN em realiza o trabalho ou de um para cada elemento do Array tudo bem tá aqui porque é agora que a brincadeira vai começar podemos definir a complexidade de beagle em o tempo linear tempo logarítmico tempo quadrático tempo exponencial tempo fatorial e tempo polinomial entender melhor esses níveis

Vamos partir para um código de exemplo até que enfim um código né a gente fez in typescript está bem simples começando Então por um código com o tempo constante com ordem de um quando não a dependência do tamanho de entrada e me se não houver dependência o tempo de execução permanecerá o mesmo por toda a parte nesse exemplo criamos uma rede de nomes que representam uma fila de cliente a função próximo atendimento retorna sempre o primeiro elemento do Array não importa o tamanho do Array pode ter de 1 a 1 milhão de alimentos Ou seja

a função exige apenas uma etapa de execução que vem sobre o tempo constante com ordem de de um tranquilo até aqui né Vamos usar mais um código agora explicando o tempo lhe né agora em nossa fila de clientes implementamos uma função chamada fila completa e as há 300 recebe uma Rei porém a forma como ele manipula esse Array é que determina a sua complexidade nesse caso percorremos através de um foco todo a e escrevemos todos os elementos no console Ou seja a função será executada do tempo pode n ou tempo linear onde ele especifica o

número de itens dentro do Array Suponha que o arredondado tem a 500 ele tem a função de escrever a 500 vezes se o número de itens aumentar a função levar a tanto tempo quanto o tamanho de n para escrever até agora tá de boas então vamos ao do tempo logarítmico eu preciso te mostrar eu esse é um gráfico de como são classificadas da complexidade na notação big-oh veja que o que aprendemos Até agora está ali na área do excelente ou de aceitável Quanto mais a complexidade vai aumentando mais vermelho vai ficando e menos eficiente será

o algoritmo que daqui a pouco a gente volta Nesse grato no algoritmo ter uma complexidade de tempo logarítmica blog higiene quando o tamanho é de entrada foi reduzido a cada etapa Isso significa que o número de operações não é o mesmo que o tamanho de entrada na verdade ele diminuirá a cada interação podemos dizer que ele segue aquela máxima de dividir para conquistar nesse exemplo temos um Array de números ordenados Nossa função faz uma busca binária onde a cada iteração no Array é preciso dividir ele em dois para saber qual lado pesquisar dessa forma um

número de operação restante vai diminuindo Ou seja no melhor caso teremos nesse algoritmo ou higiene e no pior o blogue DN Então chegou a hora de voltar naquele gráfico você consegue perceber que esse último exemplo fica na escala é do aceitável agora vamos entrar na Seara dos algoritmos considerados ruins Mas do ponto de vista de complexidade a do tempo quadrático o DN elevado a 2 Olha só esse código comecei criando uma lista de nomes de pessoas iremos combinar essas pessoas para isso na função combinar os dois loucos se o Array tiver em itens o loop

externo executará n vezes e um núcleo interno executará n vezes para cada iteração do loop externo o que dará um total de elevado a 2 nesse caso o som 10 nomes o que dará um total de cem interações porém com 90 impressões pois eu adicionei uma condição ele por uma pessoa não combinar com ela mesmo agora estamos prontos então para entender melhor um exemplo bem clássico de algoritmo com a complexidade de tempo exponencial calculando os números de Fibonacci o exemplo acima é justamente o cálculo repulsivo dos números de Fibonacci o de 2 elevado a n

especifica o algoritmo entre o crescimento é duplicado toda vez que o conjunto de dados de entrada é adicionado a curva de crescimento começa arrasa e depois sobe meteoricamente eu sei que você está em dúvida está quase indo nos comentários para perguntar se nós a função misturar vários tipos diferentes de complexidade como é que isso ser E aí essa daí é sem dúvida alguma uma excelente pergunta aliás pode comentar a vontade se você tiver alguma dúvida Ok então vamos para o código para responder essa pergunta se não tá vamos ao nosso exemplo da fila de cliente

e dentro da nossa função precisamos realizar dois núcleos de da mesma forma na estrutura mas sem alinhamento podemos dizer que é Necessário eliminar as constantes esse tipo de algorítimo o de 2n é considerado apenas o DNA quero 300 agora o exemplo da fila é uma mistura hoje o Primeiro Momento enviamos para o console o primeiro elemento do Array no fórum estão dividindo a Rê em dois e no último forte estamos percorrendo toda a estrutura dessa forma temos a seguinte notação pó de um mais n / 2 + n que no fim das contas é igual

a odiene também ou seja a complexidade continua a mesma e assim como o gráfico nos mostra o nível de complexidade é possível também transpor isso para uma tabela de acordo com o algoritmo utilizar essa tabela ilustra bem o tempo de cumplicidade dos algoritmos no melhor no pior cenário e também na média querendo ou não estamos sempre melhorando o desempenho dos nossos códigos justamente para reduzir o tempo de execução sempre tem espaço para utilizar não é verdade por isso conhecer as estruturas de dados e os algoritmos corretos para determinadas situações Faz sim de você um programador

melhor agora é um momento para você nos contar aqui nos comentários Qual foi o algoritmo mais legal e complexo que você já criou Não esquece também de responder qual seria aí um tempo de complexidade dele na notação big-oh eu quero que a gente tenha conseguido te dar uma luz no fim do túnel sobre esse assunto ainda tem muitas coisas para estudar sobre esse tema eu tenho certeza que a gente só deu uma pequena introdução uma arranhadinha nesse assunto não esquece de deixar o joinha o um comentário se inscrever aqui se você ainda não é nosso

CDF e a gente te encontra no próximo vídeo combinado combinado até lá tchau tchau tenho certeza que se você chegou até aqui é porque você quer uma nova recomendação para não ficar só com a cerveja Não claro né o vídeo acabou mas a recomendação Que tal então continuar com a gente na playlist do dicionário do programador aqui no lado você pode escolher um tema que mais te interessa a lista tem quase 200 vídeos já está em ordem alfabética bem fácil para você encontrar que você quer