Projeto e Análise de Algoritmos - Aula 03 - Análise assintótica: ordens O, Ω e Θ Parte II

[Música] Há pes sean benvidos a nosa tercera aula de proyecto y anális de algoritmos n esa aula veremos anotación omega y teta realizaremos también algunos ejercicios como ya veron aula anterior a gente precisa Fer algunas manipulaci matemáticas y precisamos también lembrar alguns conceitos matemáticas ent vamos relembrar algumas eh propiedades matemáticas que precisamos saber alén de mostrar ejercicios adicionales de anotación Omega teta y o como ya vimos la aula pasada Existen tres tipos de comparación asintótica para qué Para comparar funciónes que representan o consumo de tempo de noso algoritmos existe a comparación con sabor menor igual

que notación o que fue introduci aula pasada a comparación con sabor mayor igual para cual usada a notación oma y a comparación con sabor de igual para cual usada notación teta lembrando ent que que como era definido formalmente oo Enton sean TDN y fdn Funes inteos nrea dimos que TDN e o fdn si existen constan CN sub que TDN esa de aquí TDN e menor o igual a c de fdn para algún n sub n mayor igual a n sub n ese caso a gente vi que era que eso acontecía aquí la verdad y como

vimos un un sub podría ser cualquier un de esos valores de aquí ent realizando algunas manipula a gente puede encontrar que n sub cer 16 que n sub cer 23 que sub 29 por exemplo porque yo va ser válido para cualquer n que se mayor que eh 14 n ese caso n aproximadamente 14 acora vamos ver a notación Omega dicos que TDN oma de fdn si existen constantes positivas c sub que TDN mayor igual a c por F n para n mayor igual a ner o que de no está cuase idéntica aota o a diferencia

está exatamente en esbo mayor igual no lugar de menor igual que nota o sabor de mayor igualo no gráfico a aquí a fun TDN y fun fdn certo tn que esa de aquí a gente precisa Mostrar eh que mayor igual a c por fdn Okay aquí no início parece que a TDN es mayor igual que a c por fdn aquí noio el menor y aquí el mayor a gente precisa saber cu que ner t queo se verd se a gente aquí eso de aquí no me serve eso de aquí tamb no ahí que o n

sub ser es de aquí certo queo verd para todo n mayor igual a 35 por exemplo 36 cer está veamos alg exemplos queremos demar que 6n omn para mostrar ISO que quecos n caso a gente que usar esa expresión de de aquí encontrar c y o n subamos sempre pelo lado esquerdo para demonstrar queo verdad 6n + 5 que 6n 5 Es mayor que 6n por qu porque es de aquí un número positivo certo está F Ah Es colocar ISO ISO verdad para para qué valores de n para cualquier n mayor o igual aer Okay

ent consegui encontrar cu que me valor de c y cu que me valor de n sub 0 c 6 y n sub c0 es 0 esa de aquí estaba fácil cierto agora queremos demostrar que n cuad - 2 e oma de n cuad Okay Enton comenzamos así n cu - 2 comenzamos de ese lado siempre n cu - 2 Yo quiero llegar una expresión de un lado eh que de lado dirito teña o n cuadrado y puo colocar que n cu - 2 e mayor o igual que n cuadrado eso acontecer para algú valor de

n No no es tan fácil n caso priser alg alg para conseguir eso de Ah no verd para valor de n eso aquí no verd que queero usar un truque Ah vo dividir es n cuadrado enas partes ent vo n divir enas partes n má n eso mmo que nado certo men do verdad aquí que eso ig a eso certo igual a esa expresión de aquí yo falar que esa expresión de aquí mayor igual que n por do Sí esa parte de aquí mayor igual aer certo acora tenengo que resolver eso de aquí cuando n

cu sobre 2 - 2 es mayor o igual a cer Si resolvemos eso de ahí esa expresión es mayor igual a cer si n es mayor igual a do si n mayor igual a do lbr de a considera n positivos porque o n representa para nos oo de instancia ent agora conseguimos encontrar cual 1 aquí uc medio y que un sub 0 que ese de aquí cierto pasemos para un otro ejercicio demostrar que n log n es oma de n para probar ISO a gente sabe que log de n es mayor o igual a 1

para todo n mayor o igual a 2 cierto y por tanto n log n e mayor o igual a n o que que estamos pasendo ahí simplesmente estamos multiplicando ambos lados por n yo ser verdad tambén para todo n mayor igual a do por a gente encontró cu que valor c que y cu que n sub quee cas do viosa omora pasamos a a próxima nota que notación tet que la de igual está másque a a forma dela decos que TDN teta de fdn si existen constantes positivas c1 y C2 y n sub cer ta

que c1 veces fdn es menor igual que TDN y y Ela es menor igual a C2 de FN para todo n mayor igual n sub veamos no gráfico ent teno a fun TDN que es amarel aquí TDN y teno c1 fdn t que la menor a fdn está ent teno c1 que es azul está eno de esa amarela a partir de más o menos o valor 1 certo ahí teno un valor de un valor cer para máo que también constante C2 que tn menor igual C2 por FN c C2 por fdn C2 por FN verm

de aquí a partir de que valor má menos mayor Para mayor que TDN a a verm con amarela mayor a partir má menos de igual a1 certo esas cosas se cumpr que se FN menor igual a tn y tn menor igual C2 ve FN para que valor de n sub zer a gente p 1 p 21 cu do do a gente PR queo se verd para todo n mayor igual a ner máximo do certo máximo de n y n do que serí es de aquí es verd para todo n mayor igual exemp que1 certo como

si a función TDN esas desas otras fun de c1 fd1 y C2 fdn otra otra forma de falar mmo Dios que TDN teta de fdn si TDN o de fdn y TDN oma de fdn osas cosas juntas está veamos alguns exemplos queremos demostrar que n - 2 t de n como queoso a demostrado exercicio anterior que n cu - 2 e teta era ega de n cuad certo ent a gente demostrado n cu-2 e oma de n cuad copiar de aquí está copiado de esa esaa ao alg algas manipula alguns truques divid n cu enas

partes n cuos má n cuadrado meos de modo a depois encontrar cuá eran valores c1 y n sub1 hios todda una manipulación ahí para conseguir demostrar ISO ent está faltando verdad a demostrado eh que que n cu - 2 mayor o igual que n cuadrado cierto os demostrado Esa primera parte de aquí certo ahora está falando a segunda parora teno que demonstrar que tn menor igual a C2 por FN se comar de no n cu 2 menor igual alg Cos aquí tamos usado mayor yora que usar un menor má aquí manipula muo má simples porque

n cu men do que empre menor que n cuadrado Ah porque aquí estoy tiando estoy tiando un número do es n cuado queo de aquí verd para todo n mayor igual a cer ent esa demostración parte o ficc aquí encont que C2 igual 1 y que n sub 2 ig aquí que que demostramos que n cu - 2 e o cu ent si demostramos que oma y o a ya Demon que tet certo que a gente pris esclarecer son es n sub cu valor de c1 y cu valor de C2 certo a encontado c1 c21

a sabe que n por menor ig n 2 yor ig N y n sub n sub máximo de es do a gente vio figura anterior un máximo de n sub1 y n sub2 que en ese caso es do existen clases t nomes clases t similar o que mostre aula anterior ent temos a clase constante a clase logaritmo a clase linear n log n cuadrática cúbica polinomial y exponencial algoritmos que son de clase teta o se que son constantes no son muo rápidos ent no depende deo de entrada realizan algas opera simples t vez algoritmos que

son clase logarítmica ehes son considerados muo rápidos también un exemplo de algoritmo que que está clase teta logarítmica a a Busca a Busca binaria después temos algoritmos que son lineares eh n caso si multiplicamos o n por 10 por exemplo oño de entrada por 10 o tempo va ser multiplicado por 10 es algoritmos también son considerados muo rápidos Existen los algoritmos también n log y n está con considerando constantes razoes o se c1 y C2 y n sub a gentee considerar eles tambén eficientes exemplos de algoritmos que son cl en log son algunos algoritmos de

ordena después tenemos algoritmos cuadráticos algoritmos que que son de clase teta cuadráticos cuando multiplicamos n por 10 o tempo va ser multiplicado por 100 algunas veces es algoritmos pueden ser satisfatorios tenos algoritmos también cúbicos la clase teta cúbica cuando n multiplicado por 10 o tempo multiplicado por 1000 algunas veces también pueden ser considerados satisfatorios exemplo de algoritmos que son cúbicos eh a multiplicación de matrices un algoritmo que realiza multiplicación de matrices despos polinomia exemplo de polinomial ent T de con k mayor igual un exemplos de polinomi son linear cuadrático cúbico y cualquier polinomial n elevado

a 10 a 20 a 50 etc finalmente temos clase t exponencial n caso cuando n multiplicado por 10 oo elevado a 10es no son úteis de punto de vista prático cualquer exponenciales no son úteis alguns ejemplos de exponencial son 2 elevado n 3 elevado n 4 elevado n etcétera Existen algunas propiedades que Funes que Funes satisfacen y o om y satisf propiedades son segues transitividad reflexividad mesmo que acontece por exemplo con opera matemáticas algas algas propedades que caso de de t o y oma las cumpr propiedad transitiva qu que dice esa propiedad si TDN es

teta de fdn y fdn de gn a gente falar que TDN teta de gdn mmo para o si tn o de FN y FN o de gn ent TDN e o de y para om a reflexividad si n caso a gente afirma que TD de TDN de la mma TDN o de la mesma y TDN oma de la mesma asimétrica TDN teta de fdn si TDN teta de fdn ent fdn teta de TDN eso no verd a simétrica no verd para o y oma antisimétrica antisimétrica verd para o y om TDN o de fdn ent

fd oma de TDN o mesmo para Ah para es caso de aquí si TDN oma de fdn FN o de TDN esas propedades son importantes ve nos perer cálculos consumo deo algoritmos má rápido revisión de como veron a gente pró Deer algas manipula nos exerci para demonstrar eh si expr funn omn tn para cálculos tamb consumo de tempo a gente preciser algas opera aparecer tambén algas somas certo ent precisamos revisar alguns conitos matemáticos algas propriedades matemáticas para cálculos siar a gente priser cálculos má menos simples a no pris de saber integris eh Por exemplo trabar

con integrais que que a pris lembrar cosas de matemática precisamos saber algas propriedades con para trar con expoentes por exemplo sios x n ve x m comoos a mesma base simplesmente suamos expoentes aquí tambén x n por x m comoos aesma baseos a diferencia expoentes x n El M mesmo que x n ve es de aquí important Porque ve conf confus x n ig 2 x n c aquí que estamos usando operador no operador ve algas de logaritmos tambi pramos porque alg algoritmos con deo n log n log de namos opera con logaritmos tamb important

lbr que logaritmo de produto e a soma do logaritmos que logaritmo da división e a diferencia de logaritmos que log de B elevado a m o mesmo que m log de b y también cómo faer mudanza de de base n log de AB es o mesmo que log log base cdb dividido por log base cda más algumas otras cosas que precisamos saber es algas sumatorias en algun dos cálculos a gente precisó Fer a sumatoria de de un de 1+ 2 + 3 at n eso de aquí da n veces n + 1 sobre 2 a

sumatorias de I cuad eso de aquí da n veces n + 1 veces 2n + 1 sobre 6 a sumatorias de I cub que da Esa esa expresión de I y a sumatoria de xi para ig m atn que da esa expresión de aquí especificamente a gente podería colocar aquí cual que un resultado cuando y Igual aer vamos así a sumator que a gente usar tal vez en alg en alg exercícios que mostraremos n aulas Quiero saber para igual aer cu que resultado de X La somat de x y está resol verd dar aquí x

n+ su menos y aquí Si a gente multiplica va dar x elevado a m si m ig a 0 va dar x elevado a 0 ent aquí va dar 1 x elevado a 0 da 1 y aquí en baixo Fica x - 1 está ent esa de ahí veces a gente va a que utilizar aquí tenos un ejercicio dici queos que realizar algas opera y a gente ve Fica asustado con expreses má o que que a gente de de saber Ah a gente de saber cu que a definición formal de cada nota tentar usar esa

definición formal tarer manipula matemáticas para conseguir lar no que queremos no que deseamos dem Mostrar por exemplo aquí temos un exemp que parece difícil temos queremos demostrar que de un t1 de n t2n ig o de f2n supondo que t1n igual o de f1n y t2n ig o f2n e y f1n igual f2n Ah pare confus cabe un no cabe que queos simplesmente aplicar a definición formal de o caso y vemos o que que verdad Aquí está falando que eso de aquí verdad que eso de aquí verdad Y que eso de aquí verdad y que

que queremos Mostrar eso que está en laran certo si esas TR expres son verdad ent a gente sabe que n primero caso existen constantes queo verd aquí para primero de aquí existen constantes positivas y n sub1 que de n menor ig C de FN para todo n mayor igual a ner eso de aquí verd de que a defini se cumpr que c1 y n exist que son alg valores que que exist mmo para segunda expr que exist constantes positivas c22 t que2 men igual C2 f2o de aquí V definición direta de o y tamb que

eso de aquí verdad porquees falar Ahí ent existe constantes positivas C3 y sub que aquí f1n menor igual constante ve f2n para todo n mayor n3o defini formal de o Okay Esas tras que son verdad quiero mostrar laran aquí o que que queer con esas expr para laran vamos aos priso lado esero t2n okay de aquí para ladoo pensando Prim parte que prisar conas TR ina aho vamos esas certo vamos suar esas que ficar t1n c2n menor igual a c1 f f1n C2 fpr de aquí cons de aquí ladoo f2 ladoo f1 f2 Okay f2

F está meando otra expr queo usar esa de aquí como FAO ent para incluir esa expr aquí Ah que F de1 es menor o igual a C3 f2n Okay aquí teno f1 vamos substituir ent ese f1 por esa expr de aquí ent ficar c1 que f1 menor igual a C3 f2n colocar esa expr aquí colocar aquí menor igual certo Demis igual ent que expr ladoo que f2 certo aquí colar en evid f2n yar c1 C3 C2 y okay Que quer lado2 y lado expr constante aquí ve f2 cu que valor constante de aquí certo a

constante c c1 ve2 y sa máximo de toos n queos aquí consim res un exer que par difíc aplic defini yer algas manipula matemáticas para no que a a nosa tera aula de proeto y anál de algoritmos que algas cosas matemáticas que prisar revisar para próxima a Espero que saoo lbr todas esas cosas y eh nos vemos aula número cuatro espero quean [Música] gado [Música] [Música] ah [Música] foreign