Ordem de Grandeza em Análise de Algoritmos

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Fundamentos Matemáticos para Computação - Ordem de Grandeza

Olá, alunas e alunas do curso de Fundamentos Matemáticos para a computação.
Mesta videoólogo, eu vou falar da ordem de grandeza.
Eu vou começar definindo o conceito de ordem de grandeza, mostrando como se é relacionado com a análise de algoritmos e por último como podemos fazer o uso do teorema mestre para avaliar esses questões de desempenho.
Bom, a ordem de grandeza é uma maneira de você estar comparando funções.
Isso pode ser feito, digamos, assim, através da taxa de crescimento de funções.
Então, como se observa aqui, nós temos a função quadrática, bem evidente que a função quadrática cresce mais rápido do que a linear.
Bom, então, considera que tem uns duas funções no domínio dos reais no negativo, ou seja, positivo ou novo, e a função F tem a mesma ordem de grandeza do que G.
Isso vai ser denotado por F igual a Teta G.
Isso vai acontecer se existirem constantas positivas, N zero, C1, C2, TASQ.
A partir de um valor de N zero, de X, maior igual a N zero, nós determinamos esses constantes de modo que essa desigualdade se verifique.
Esse gráfico aqui representa bem essa ideia desse conceito, que é o que.
Nós temos a partir de um valor N zero, a função F localizada em termos de ordem de grandeza entre a função entre C2 vezes a função G e C1 vezes a função G.
Bom, falando numa linguagem mais próximas de conceitos que vocês já viram no que no curso, nós temos que F e G, que rostabelece uma relação binária entre F e G, definida por isso, que acabamos de estabelecer a determinação de constantes positivas N zero, C1, C2, TASQ, a partir de X, maior igual a N zero, a desigualdade se verifica, que nós estamos representando F igual à TASQ.
Então, a relação R, ela é uma relação de equivalência, lembra? Isso significa que ela estabelece, que ela particiona, nós temos classes de equivalência.
Bom, F igual à TASQ, então é um abuso de notação, isso que é dizendo a verdade, que é F pertência a classe de G.
Quando nós conseguimos relacionar as funções desse jeito, então isso começa a ficar mais claro, o significado, desce, do que foi estabelecido inicialmente, começa a ficar um pouco mais claro.
Então, vamos ver isso outra vez um exemplo, considera que F de X nesse conceito, que seja o 3x², G e G, seja 20x² mais 140x mais 7.
Subestitu ainda aqui na expressão, nós temos então que achar quem é esse C1 e esse C2, que vai ser desfazer essa desigualdade.
Bom, observando aqui, a gente precisa, então, nesse caso, focar no termo quadrático, observamos aqui um 200, então esse C1, pode ser um, porque essa desigualdade está dada aqui, com 200 vezes X².
Agora já o C2 não, porque 200, eu quero que 3x² seja maior, igual a que esse termo que tem 200 vezes X², então o ideal que o C2 seja, por exemplo, um sobre 100, porque é um sobre 100, porque vai me levar nessa expressão 2x² mais 1,4x mais 0,07.
Então, agora eu tenho 3x², a do maior é igual a 2x².
Será, lembre-se do N0.
Então, vamos ver o X, eu tenho o C1 igual 1, o C2 igual 1 sobre 100, mas vamos ver essas desigualdo, o comportamento dessas desigualdade.
Se um X for igual 1, ou seja, eu tomando o N0 como 1, eu observava que essa desigualdade não verifica daqui para cá, o 1.
3x² não vai ser maior que esse termo aqui para X².
Por outro lado, para X², isso se verifica, que dizia, a partir de X², isso se verifica.
Então, eu me encontrei no N0.
Não isso quer dizer que para X², eu vou tentar o N0 falando 2, que torna vale do C1 igual 1, C2 igual 1 sobre 100, para modular esse crescimento da minha função, ou seja, para ter essa minha função em relação à G, dentro desse gráfico aqui, como apresentado aqui.
Nós acabamos de descobrir o C1, C2 e o N0, que permite isso para esse F, para essa G.
Exerto? Bom, agora, pensando mesmo na notação e na questão de pertencer a classe de equivalência, ou de ser que vamos provar que F, pertencer a classe de equivalência de X² não ocorre para Fx igual X, ou seja, Fc teta X² não vai acontecer para Fx igual X.
Bom, vamos então lembrar que a gente teria que verificar, para caso isso fosse verdade, que seria essa condição, e, por absurdo, vamos supor, então que o Fc já que ele satisfaça isso aqui.
Se ele satisfaça isso aqui, existe em Ch0 e a desigualdade ocorre, ou seja, C1 Gx, vai ser o X², o Fx vai ser o X, então, C1 Gx² é maior e igual a X.
Como o meu X é maior e igual a N0, que é positivo, então eu tenho, o meu C1, X² é maior e igual a X, eu posso dividir por X, não tenho C1, X é maior e igual a C2, X².
Então, eu também posso dividir pelo X e ter 1 maior e igual a C2, X, ou seja, ser um X maior e igual a 1, que é maior e igual a C2, X.
Isso segue para X maior e igual a N0, já que eu estou supondo que isso aqui ocorre.
Vou tentar não provar por absurdo, vou ter que caindo uma contradição, e a contradição caia aqui, nesse lado, observe que 1 maior e igual a C2, X implica em, posso passar o C2 para o outro lado, que é uma constante positiva, não soube C2, maior e igual a X, só que são absurdo, eu vou ter valor de X, que para um C2 fixo, eu encontro um X, suficientemente grande, tal que passe ocorrer X maior e igual a um subcedor.
Então, não é válido, que essa desigualdade ocorre para qualquer valor de X, então, eu cheguei num absurdo.
Bom, dito isso sobre a ordem de grandeza, vamos agora analisar o conceito, a inicia a ideia da análise de algoritmo, a ordem de grandeza acaba sendo muito importante na análise de algoritmo, porque, nessa análise de algoritmo, nós temos que identificar as tarefas mais importantes que são executadas por ele, e o número de vezes que as tarefas estão sendo executadas, e isso vai depender muito do tamanho dos dados de entrada.
Então, nós temos que ter funções que, aí, que entra a ordem de grandeza, que expressa a quantidade de trabalho que o algoritmo vai ter para processar esses dados de entrada, mas domínio N, considerando o tamanho N de entrada.
Bom, então, vamos tentar ir nos traçar a dificuldade, como a gente avaliia isso através de um exemplo, aqui considerando o problema de ordenar 10 milhões de números.
Então, suponha que eu tenho computador A, que é uma verdadeira Ferrari, eles executam 1 bilhão de tarefas, por segundo.
Uma excelente programador, nesse kit, que implementam o algoritmo X para solucionar esse problema.
E esse programa dele é tão bom que ele utiliza a linguagem de máquina e, bolou o algoritmo X, que ele mediu, que tem uma performance de 2 vezes o tamanho da entrada ao quadrado.
Beleza.
A outra equipe, o que? A outra equipe já trabalha no móvel carroça, digamos assim, ela vai ordenar 10 milhões de números, mas com um programador com nível mediano que implementam o algoritmo, mas ele propõe o algoritmo I, o seu ompar solucional problema, que ele implementou em linguagem, seca uma linguagem de mais alto nível, em um computador B, que executa 10 milhões de tarefas por segundo, nossa carroça aí.
Essa implementação consegue solucionar, pelo que ele me dio de perfomas, assim, estão-seis do problema, na fase com uma performance de 50 vezes o tamanho de entrada, log na base 2 do tamanho da entrada.
Então, agora vamos calcular e ver quem ganha, para ordenar os 10 milhões de números, que são o que? Que representam uma entrada a N de tamanho 10 elevada a 7.
Bom, fazendo essas contas, nós vamos ter aqui, pro algoritmo I, que ele tem uma performance de 2 vezes o tamanho da N, e vezes o tamanho da entrada é o quadrado, mas ele fazem 1 bilhão de dados por segundo.
Só que nessa conta aqui você vai obter 20 mil segundos, que dá um pouquinho acima de 5,5 horas, agora vamos para a carroça.
Você vai ter 50 vezes o tamanho da entrada, vezes o log na base 2, desde esta mãe da entrada, dividido por pelo fato de que ele opera com 10 milhões de dados por segundo.
Fazer uma entrada a 7.
Fazer essa conta, você vai ter 163 segundos, ou seja, em menos de 21 minutos, tendo programado em C e num computador A, que sem ter um computador A, que era mil vezes mais rápido, do que o computador B, que utilizado aqui.
Bom, nós vamos então a diferença aqui, 17 vezes superior, para o algoritmo A, temos gastos de tempo.
Bom, o que isso que eu dizia? Diferentes algoritmos que solução no mesmo problema, eles podem ter diferenças significativas em termos de efficiency.
Tais diferenças, elas acabam sendo muito mais relevantes do que diferenças de hardware e de software, daí a importância do projeto e da análise de algoritmo.
A eficiência não requer sobre o tipo de linguagem, que nem a gente viu, utilizada para implementar o algoritmo, nem sobre o tipo de máquina na qual o algoritmo é executado.
Ela tem a ver com como você vai serficiente.
A eficiência de algoritmo ela pode ser definida pela sua complexidade de tempo.
Conta você ser eficiente em termos de tempo, por exemplo.
A complexidade de tempo, então ela vai ser dado pelo número de instruções básicas que o algoritmo executa considerando o tamanho da entrada.
Então com que lida, principalmente eu me diria que essa entrada cresce crescimento.
Então nós temos aí um análise, que na verdade é uma análise asymptótica, ou seja, nós consideramos, nós falhamos quando esse tamanho de entrada se torna muito grande.
Vamos estabelecer um outro conceito aqui, voltando a nossa função fg definida dos reais positivos ou nulos, a função f será ó grande, que é uma outra notação de g, denotada por f igual a ó grande gg, e se existe constantes positivas n zero e c task para x maior igual a n zero, fg é menor ou igual a c de gg.
Então agora aqui eu já não estou colocando uma faixa, não é um limite inferior.
Essa notação ó ela considera algo mais fogado no sentido de que ele está abaixo dessa gg.
Bom, isso quer dizer que f cresce a mesma taxa ou uma taxa menor como gáfico de chovo do que g.
Se soubermos de fato que f cresce uma taxa menor, podemos dizer que f, então é ó pequeno de gg, isso é denotado por f igual a c, um minúsculo de gg.
Então se a gente for pensar assim de uma maneira bem básica a respeito dessas notações, a gente pode pensar que ó grande ou pequeno se relaciona da seguinte forma.
Nós não estique f sendo ó grande g, então ou ela é teta de g ou se joelha estar ali entre um limitante superior ou inferior dessa g, para ter minadas constantes ou ela está abaixo mesmo dessa gg.
Isso é semelhante dizer que a gente está fazendo uma comparação de menor ou igual, então ela pode ser igual que seria o caso teta, pertencia aquela classe ou não, sem menor, estretamente menor.
Pense, voltando aqui no minutinho, pense naquela questão da classe, que é, pertencia a classe, quando ela é igual ou ela pode estar fora dessa classe, que ela está menor, ela é menor.
Bom, vamos, então já que estamos falando de análise de algoritmos, vamos ver um algoritmo, e aqui nós vamos começar a fechar vários pontos a respeito de tudo que vocês viram no comproço até agora.
Suponha que eu tenho, então, ter B como sendo uma função de complexidade, e B é um número de vezes que teremos que multiplicar a base para obter a explodênciação aqui.
Então eu estou fazendo A elevado a B nesse caso, desse algoritmo aqui.
Bom, o que está acontecendo? Eu faço uma comparação, eu tenho uma instituição de comparação, um retorno, eu tenho, se a comparação não for obedecida, ocorreu, eu vou ter um retorno, se não, eu vou ter esse resultado aqui, que é um produto, nessa linha 3 de escopro, eu vou ter um produto e uma chamada recursiva, beleza? Então, bem agruçou um modo, eu poderia dizer que a minha função Tb, ela é, a chamada recursiva mais essas quatro instruções aqui.
Toda vez que o chama recursivamente, eu estou fazendo isso.
Reparou que é uma relação de recorrência, onde eu estou contando o esforço computacional que eu tenho, o tempo que eu estou, os forços computacional que eu tenho, ou por exemplo, pensando em outro jeito, o tempo que eu estou gastando fazendo esse iF, retornando isso aqui, eu fazendo produtos, fazendo a chamada recursiva, todas essas estemos sendo computados aqui.
Então, através de uma relação de recorrência, se eu expande isso, eu vou verificar, eu vou chegar nesse termo, esse termo aqui é uma função, lembre-se de funçalo, é uma função linear.
Então, eu tenho que o meu Tb, ele é uma, ele é teta de b, ou seja, ele pertence a classe dele, pertence a classe de uma função linear em d.
Então, nesse caso, d, um linear, o quadrático, eles são polinômios.
Um algoritmo polinomial é aquele que gasto um tempo limitado por um polinomial para se alucinar instâncias desse problema.
Então, se existe um algoritmo polinomial para um problema computacional, bom, o problema é classificado como um problema polinomial.
Os problemas, porque eu disse bom, porque os problemas polinômios são considerados tratáveis.
Você consegue ter um algoritmo, você consegue ter uma solução em um tempo polinomial.
Agora, problemas para os quais não existem o algoritmo polinomial são ditos intratáveis.
Então, eles podem ser muito lentos com o tempo na ordem de 2, ele vai dar n, 3, 5, n, por aí vai.
Bom, assim chegamos no teorema mestre, porque reparem que a gente viu os pandas, os põe verificas ali para definir o ordem linear daquela análise que nós fizemos, mas vira em vez de nós caímos em relação de recorrencia para representar algoritmos.
E através do teorema mestre, nós podemos analisar o comportamento dessas relações de uma forma mais direta.
Eu não vou fazer a demonstração do teoreno, mas é importante nesse curso que vocês saibam interpretar esse teoreno.
Então, nós temos aqui considerando uma relação de recorrencia, se um maior e igual zero é um SM dado por álcool, eficiente A, S, D, N sobre V, mas N elevado assim.
Então, a minha função G tem esse formato.
Bom, N pode ser B elevado a M, lembra que nós já tínhamos visto isso naqueles algoritmos de divisão pro conquista e considerando 2 EVE para a tua A, A, B são inteiros, A, A, A e B, A e C, um número real não negativo.
Bom, B e A, A e A.
Ainda nós vamos ter a seguinte relação.
Se você estiver em determina, por exemplo, que é a complexidade, contando as instruções, ou faz uma análise e estabelece essa relação de recorrencia desse tipo para o seu ocorítimo, você pode, pelo teoreno M, C, D, D, C, que se há a fome menor que B elevado a C, a fome na fechada, nós não vamos expandir isso por ele verificar.
Nós vamos dizer que a fome na fechada disso, que é essa relação de recorrencia, esse ocorítimo, ele é da ordem, ordem de grandeza dele, em função mutama ainda entrava, é ter da D, N elevado a C.
Se o aforigou a B elevado a C, essa ordem é N de c vezes log de N.
E se for maior, essa ordem é N de elevado a log de A na base B, considerando a A e o B aqui, ditos.
Então vamos brincar desse conceito, que é o mais importante que vocês entendam que a relação de recorrencia pode representar uma maneira de fazer o cálculo da complexidade e que não necessariamente a gente vai precisar chegar à fome na fechada para deduzir a ordem de grandeza desse algoritmo, a gente usa o teoreno Mestre.
Então aqui o S, N, se ele for cidado desse jeito aqui, nós vamos identificar o A, o B, o B, o B, o C, o C, o 3.
Dessa forma nós temos o A igual a 4, que vai ser menor que o B elevado a C, que é o 5 elevado a 3.
Então caiu um no caso um do teoreno Mestre.
Isso significa, pela nossa relação de recorrencia, ele é teta de N ao cumpo.
Certo? Bom, outro exemplo está aqui.
O meu A agora é 1, B igual a 2, e C igual a 0.
E nesse caso, então nós vamos ter que A vai ser igual o B elevado a C, vai ser 2 elevado a 0, que também vai dar 1 caímos no caso 2 do teoreno Mestre.
Isso significa que nós vamos ter N elevado a C, log de N, o que nos faz.
N elevado a 0, log de N, o que nos leva um teta log N, a ordem de grandeza, é a plova ritmica.
Certo? Bom, espero que vocês tenham entendido.
São o uso do teoreno Mestre, praticem nos exercícios, leiam a sessão 5.
5, e paramos por aqui na aula de hoje.
Muito obrigado pela atenção.