7/24/2019 I Resumen No Numrica 2

1/2

I Resumen No Numrica 2

Anlisis a Priori:su objetivo es obtener una funcin el cual limita el tiempo de computacin delalgoritmo, se limitar a contar las veces que la instruccin ser ejecutada, ste nmero puede serdeterminado independiente de la mquina en la que se ejecute, tambin tiene como objetivo ladeterminacin del orden de magnitud del algoritmo.Anlisis a Posteriori:su objetivo es la recoleccin de estadsticas acerca del consumo de tiempo

y espacio del algoritmo durante su ejecucinOrden de magnitud:de una instruccin se refiere a la frecuencia de su ejecucin mientras que elde un algoritmo se refiere a la suma de las frecuencias de las instrucciones que lo componen

Notacin Asinttica:Notacin O, se utilia para e!presar el lmite m!imo. "efinicin# f$n% & O$g$n%% s y slo s e!istendos constantes positivas c y nO tales que 'f$n%' ( c'g$n%' para todos los n)nO. *uando se deseadeterminar el orden de magnitud de f$n%, siempre se trata de obtener el g$n% ms peque+o tal quef$n%& O$g$n%%eorema -.-# i /$n% & am n

m010a-n0a2 es un polinomio de grado m, entonces /$n%&O$nm%

3ara e!presar los valores mnimos, tambin e!iste una notacin. "efinicin# f$n% & 4$g$n%% s y slos e!isten constantes positivas c y nO tales que para todo n)nO, 'f$n%') c'g$n%'5 si los dos son iguales se usa

uma de enteros $preguntar si va%

Estructura de datos Elementales:arboles, grafos y conjuntos.

Arboles:conjunto finito de uno o ms notos tales que e!iste uno llamado ra y el resto estnpartidos en n)2 conjuntos disjuntos -..n los cuales son de por s un rbol y se denominansubrboles de la rai.

6rado# es el nmero desubrboles

Nodo terminal# nodos quetienen un grado igual a cero,tambin llamados 7ojas, otrosnodos se llaman no terminales

8ijos# los nodos de lossubrboles de un nodo 9.9# padre de sus 7ijos.Nodos 8ijos de un mismopadre se llaman 7ermanos

:l grado de un rbol es el m!imo grado de los nodos de ese rbol.Nivel# se define dejando que la ra tenga el nivel -, se dice que un nodo est en el nivel p, si sus7ijos estn en el nivel p0-

/ltura o profundidad# de un rbol es el nivel m!imo de los nodos del mismo;osque# conjunto de n)2 rboles disjuntos. i le quitamos a un rbol su ra obtenemos uno.

"atos# info contenida en elnodo

# apuntador al siguientenodo

/6 $-% apuntador $2% info

Arboles Binarios:conjunto finito de nodos el cual es o bien vaco o consta de una ra y ? rbolesbinarios disjuntos llamados subrboles iquierdo y derec7o

Lemma 1# el m!imo nro de nodos en el nivel i de un rbol binario es ?i@-. :l nro m!imo de nodosque puede tener un rbol de profundidad > es ?A@-, AB2

7/24/2019 I Resumen No Numrica 2

2/2

en la ra, para usar el 7eap como cola de prioridad es necesario que podamos insertar o removerel elemento ms grande en cualquier momento

Ga! 7eap# el valor de cada nodo es igual o mayor que el valor de sus nodos 7ijosGin 7eap# el valor de cada nodo es igual o menor que el valor de sus nodos 7ijos

8eapify#

*onjuntos y Hnin de *onjuntos "isjuntos#