00:00:00
[Música]
00:00:00
notaciones sintética una forma en la que
00:00:03
los libros de ciencias de la computación
00:00:05
pueden explicar mucho más de los
00:00:07
algoritmos cuando termine este vídeo
00:00:09
podrás entender e interpretar cada parte
00:00:11
de la definición formal de cualquier
00:00:13
notación asintótica ya vimos qué es la
00:00:16
complejidad en el tiempo o complejidad
00:00:18
temporal existen algoritmos que pueden
00:00:21
tardar más tiempo mientras procesan más
00:00:23
datos lo podemos ver representado en
00:00:25
gráficas con lo que ya nos es mucho más
00:00:27
sencillo comparar el tiempo pero cómo
00:00:30
podemos clasificar estos resultados
00:00:33
cómo funciona la notación asintótica
00:00:37
[Música]
00:00:44
digamos que tengo un algoritmo que
00:00:45
ordena números y es bastante bueno
00:00:49
he calculado el tiempo con el que lo
00:00:51
hace y más o menos obtiene esta forma de
00:00:54
crecimiento como complejidad en el
00:00:56
tiempo nada mal verdad bueno luego el de
00:00:59
probar y obtuvo esta forma y lo volvía a
00:01:02
probar de nuevo y obtuvo esta otra forma
00:01:04
siempre tiene variaciones en el tiempo
00:01:07
en el proceso a veces tarda más y a
00:01:09
veces menos y estos pequeños detalles me
00:01:12
resultan en dos problemas primero se me
00:01:15
hace muy complicado escribir la
00:01:17
expresión o fórmula que describe el
00:01:20
crecimiento del algoritmo y segundo el
00:01:22
algoritmo cambia cada vez que vuelvo a
00:01:24
medir lo bueno una de las formas en que
00:01:27
puedes haber pensado para resolver este
00:01:29
problema es que al igual que redondeamos
00:01:31
o aproximamos un número para volverlo
00:01:34
más simple y sencillo de leer
00:01:35
interpretar también podemos simplificar
00:01:37
la forma de la complejidad temporal y
00:01:40
obtener algo más compacto y útil con qué
00:01:43
trabajar lo cual se traduce a esto
00:01:45
imagina este escenario que están por
00:01:48
servir algún refresco y te dan escoger
00:01:50
el vaso con el que puedes tomarlo tú
00:01:52
siempre dijeras el vaso con el que pueda
00:01:54
servirte una bebida sin qué
00:01:56
esta se derrame en otras palabras el
00:01:58
límite de la bebida no debería
00:02:00
sobrepasar el límite del vaso o el
00:02:02
límite superior del vaso que es lo mismo
00:02:04
este pequeño concepto nos ayuda a
00:02:06
nuestro problema porque yo quiero estar
00:02:08
seguro que mi algoritmo no crecerá
00:02:11
demasiado en el tiempo que tiene un tope
00:02:13
o límite máximo de la misma forma que no
00:02:15
quiero que el líquido rebalsa el vaso
00:02:18
para describir este límite o tope máximo
00:02:21
usamos la notación asintótica la
00:02:25
notación en sí nos ayudará a librarnos
00:02:27
de complejas expresiones polinómicas que
00:02:29
hacen esas formas de crecimiento y
00:02:31
además nos dice mucho sobre la
00:02:33
eficiencia del algoritmo
00:02:36
por ejemplo big joe o mutaciones
00:02:38
sintéticas de límite superior escrito
00:02:40
con una mayúscula y unos paréntesis
00:02:42
donde se aloja alguna forma de
00:02:44
crecimiento ya sabes como constante de
00:02:46
lineal o polonia
00:02:47
básicamente encontrar byc de un
00:02:49
algoritmo es encontrar una forma de
00:02:51
crecimiento que siempre será mayor o
00:02:53
igual que la complejidad temporal del
00:02:56
mismo algoritmo en nuestro caso podemos
00:02:58
estar seguros que en esta forma de
00:03:00
crecimiento lineal o peak adn siempre
00:03:03
estará igual o por encima de la
00:03:05
complejidad en el tiempo de un algoritmo
00:03:09
vick y así representa el límite superior
00:03:12
de la complejidad en el tiempo siempre
00:03:16
cuando decimos algo como el algoritmo
00:03:19
azul tiene adn queremos decir de que si
00:03:22
midiéramos y gráfica damos el tiempo
00:03:24
empleado cuando procesamos más datos
00:03:26
tendríamos algo que no debería
00:03:28
sobrepasar a n
00:03:30
el segundo es el libro y es exactamente
00:03:33
igual a vigo excepto que mientras se
00:03:37
ocupa de un crecimiento igual o mayor al
00:03:39
algoritmo yield
00:03:40
sólo será mayor al algoritmo no igual
00:03:43
big es mayor o igual vídeo o sólo mayor
00:03:49
bueno a partir de este punto vamos a
00:03:51
empezar a llamar a la complejidad
00:03:52
temporal como la función de rn donde n
00:03:56
representa el tamaño de los datos
00:04:00
estamos aprendiendo sobre la anotación
00:04:02
asintótica pero que representa la
00:04:04
palabra asintótica pues las cintas son
00:04:07
funciones que pasan muy cerca a otras
00:04:10
pero nunca se toman o cursan como es el
00:04:12
caso del old vic o leader
00:04:15
aunque tiene apariencia de funciones no
00:04:17
lo son solamente son notaciones es decir
00:04:20
igual podríamos decir algo común el
00:04:23
límite superior de cumpliendo estas
00:04:26
condiciones y con la forma de que
00:04:28
escribir vic y compar de asís y una
00:04:31
forma de crecimiento quieren decir lo
00:04:33
mismo en nuestro lenguaje representan lo
00:04:35
mismo por ello hay que dejar en claro
00:04:37
que no son funciones en sí más lo que
00:04:40
está dentro de los paréntesis si es una
00:04:43
función que en esencia grafica el
00:04:45
comportamiento de este límite superior
00:04:47
por ejemplo lineal exponencial constante
00:04:50
etcétera a esta función la llamaremos
00:04:52
gdn si juntamos estas dos piezas nos
00:04:55
queda una definición más clara
00:04:59
bueno ahora digamos que tengo un
00:05:01
algoritmo con un crecimiento de
00:05:03
complejidad como este crecimiento
00:05:05
constante entonces le corresponde un
00:05:08
crecimiento constante de vic o de 1 pero
00:05:11
esto no rompería la regla sobre que el
00:05:13
límite superior que de n debe estar al
00:05:16
menos arriba del crecimiento o tdn es
00:05:19
decir mayor o igual que la complejidad
00:05:21
temporal cdn vale 1 qué pasaría si lo
00:05:25
multiplicamos por cuatro pues haríamos
00:05:27
crecer lo suficiente a la gráfica de la
00:05:30
función para que cumpla la regla y listo
00:05:32
pero que ese es el número bien recuerda
00:05:36
la regla anterior pues está algo
00:05:37
incompleta resulta que también tenemos
00:05:39
una constante que va acompañada a la
00:05:41
función cdn concretamente una constante
00:05:44
sea multiplicada por gn entonces becomes
00:05:48
sería algo como constante multiplicada
00:05:50
por gdn es mayor o igual que tdn y el
00:05:55
líder sería constante multiplicada por
00:05:58
gdn es mayor que
00:06:01
ahora como esta constante nos ayuda en
00:06:04
nuestro objetivo por cumplir la
00:06:05
condición de bic ou o de cualquier otra
00:06:08
anotación fíjate si tuviésemos por
00:06:10
ejemplo la complejidad temporal como 2 x
00:06:13
en el cuadrado un pico de en el cuadrado
00:06:16
no es suficiente porque 2 x en el
00:06:19
cuadrado es mayor en el cuadrado en vic
00:06:22
ou la complejidad del tiempo no debe ser
00:06:24
mayor a la gráfica de crecimiento gdn
00:06:26
sino al revés así que lo multiplicamos
00:06:29
por alguna constante como 2 3 o 4 por
00:06:33
ejemplo de tal forma que ahora sí
00:06:34
podemos cumplir con la regla ahora si la
00:06:37
complejidad en el tiempo es menor o
00:06:39
igual que en la gráfica de crecimiento
00:06:41
recuerda que si no tuviésemos esta
00:06:43
constante c luego no podríamos seguir la
00:06:46
regla establecida que sin embargo esta
00:06:48
constante no es incluida dentro de los
00:06:50
paréntesis de la anotación de víctor o
00:06:53
de libia
00:06:54
o de cualquier otra anotación en
00:06:56
cualquier nota si no sintética queremos
00:06:58
mantener las cosas simples y la
00:07:00
constante queda relegada a permanecer
00:07:02
solo en la condición formal simplemente
00:07:05
está allí pero no aparece
00:07:07
una última cosa esta constante es un
00:07:10
número positivo o dicho de otra forma
00:07:11
cualquier número mayor a cero esto
00:07:14
porque se adopta algún número menor o
00:07:16
igual a cero cuanto lo multiplicas
00:07:18
porque éste o bien es cero a lo largo de
00:07:21
la línea recta o decrece en el eje
00:07:23
horizontal vamos a recordar cómo se
00:07:25
conecta a toda esta nueva información
00:07:26
con los algoritmos tenemos un algoritmo
00:07:29
y queremos saber cuánto demora se
00:07:31
aumentamos el tamaño de los datos de
00:07:33
entrada es decir la complejidad temporal
00:07:35
esta complejidad puede ser clasificada
00:07:38
como notación asintótica existen varias
00:07:41
notaciones y cada una se rige por
00:07:42
distintas condiciones como bic
00:07:45
donde requerimos una función de
00:07:46
crecimiento gdn multiplicada por una
00:07:49
constante que sea mayor o igual a la
00:07:51
complejidad genial ahora pasamos a un
00:07:54
concepto igual de importante llegamos
00:07:56
que tenemos una asombrosa lista de
00:07:58
algoritmos cada algoritmo con su propia
00:08:00
complejidad de tiempo aproximada así que
00:08:03
sólo tomando la complejidad temporal de
00:08:05
los algoritmos podemos deducir su
00:08:07
notación asintótica n es pico de n
00:08:10
logaritmo de n
00:08:11
big show de logaritmo de n 1 es bicol de
00:08:14
1 y luego 2 por n 1 es bic adn cada
00:08:20
complejidad y cada anotación son las
00:08:21
mismas excepto en esta última porque
00:08:24
cuando queremos convertir la complejidad
00:08:27
temporal en notación vigo tomamos sólo
00:08:30
el término de mayor crecimiento que
00:08:31
significa esto
00:08:33
tomemos la expresión anterior 2 por n 1
00:08:35
vamos a dividirla para graficar cada
00:08:37
parte
00:08:39
[Música]
00:08:42
ahora que la gráfica hemos podemos
00:08:44
comparar las mejores notas como 2 por nk
00:08:47
s más que el término 1 de hecho si le
00:08:50
quitamos el factor de 2 sigue
00:08:51
manteniendo esta característica como si
00:08:53
dominará por sobre los demás términos
00:08:56
tomando en cuenta cuál es el término que
00:08:58
crece más ya no nos es importante
00:09:00
escribir los demás términos pues sus
00:09:01
efectos no son tan relevantes no marcan
00:09:04
una diferencia al ser escritos así que
00:09:07
los obviamos los descartamos es así como
00:09:11
2 por n
00:09:12
uno se convierte en vic o dn más
00:09:15
ejemplos imagina que tomamos 3 x más el
00:09:19
logaritmo de n + 1 y también lo queremos
00:09:21
convertir anotación asintótica cuál es
00:09:24
el término que crece más separamos los
00:09:26
términos los comparamos entre sí
00:09:29
y obtenemos que 3 x n es el mayor los
00:09:34
factores no nos interesan porque con o
00:09:36
sin ellos igualmente el término mayor
00:09:38
puede dominar sobre el resto siempre nos
00:09:40
concentramos en el grado mayor es
00:09:43
necesario tomar lápiz y borrador y
00:09:45
comprarlos gráficamente no te he
00:09:47
mostrado el funcionamiento interno pero
00:09:49
puedes usar una guía bastante rápida
00:09:51
para pensar en cuál es el término de
00:09:53
mayor crecimiento aquí los ordenó desde
00:09:56
los más grandes hasta los más pequeños
00:09:58
genial ahora mira esta gráfica entre la
00:10:00
complejidad temporal y una función de
00:10:02
crecimiento lineal hay algo nuevo aquí
00:10:04
ya nos preguntamos cuál es la
00:10:06
complejidad vicaut de esta gráfica y
00:10:08
luego cuáles son las reglas son las
00:10:09
condiciones listadas de todo esto ahora
00:10:11
nos preguntaremos desde cuánto se
00:10:13
cumplen las condiciones voy a darte más
00:10:15
contexto cuando la complejidad temporal
00:10:18
es menor que el crecimiento original
00:10:20
en esta parte durante toda esta área
00:10:23
verde la condición se cumple y en
00:10:26
esencia quiero que te concentres en este
00:10:28
límite de aquí o mejor dicho este
00:10:30
pequeño punto en la gráfica llamado n
00:10:32
sub 0 básicamente firmamos que desde un
00:10:35
punto en el sub 0 cualquier número de
00:10:38
adelante hacia la derecha cumple con la
00:10:40
condición o en otras palabras cosas como
00:10:42
estas no pueden suceder donde al
00:10:46
principio parece cumplir con la
00:10:47
condición pero luego no mientras exista
00:10:50
un punto n sub cero donde todos los
00:10:52
números que le siguen cumple con la
00:10:54
condición anterior entonces hemos
00:10:56
completado la definición de anotación
00:10:58
qué sucede si no tuviéramos un punto en
00:11:01
eso pero si no lo establecemos luego no
00:11:03
podemos estar seguros de qué sucederá
00:11:05
cuando el tamaño de los datos crezcan
00:11:08
y no queremos este tipo de situaciones
00:11:11
continuamos con más notaciones vic omega
00:11:15
el límite a sintético inferior
00:11:18
un algoritmo tiene una complejidad
00:11:20
temporal que la vez tiene la anotación
00:11:22
bica o mega cuando el crecimiento se
00:11:24
multiplica por alguna constante que es
00:11:26
menor o igual que la complejidad
00:11:27
temporal aquí es al revés
00:11:29
vamos a construir esto gráficamente
00:11:31
[Música]
00:11:32
cuando la complejidad temporal está
00:11:35
sobre la función de crecimiento
00:11:37
multiplicada por alguna constante desde
00:11:40
n 0
00:11:42
luego tenemos líder omega con muy
00:11:45
parecida a big omega salvo que esta vez
00:11:47
en lugar de especificar menor o igual
00:11:50
simplemente es menor
00:11:51
[Música]
00:11:52
la diferencia es muy sutil
00:11:54
[Música]
00:12:02
y finalmente viqueira esta es curiosa ya
00:12:05
que tenemos una función de crecimiento
00:12:07
que intenta igualar a la forma de la
00:12:10
complejidad temporal y al menos tenemos
00:12:12
dos constantes capaces de rodear la
00:12:14
complejidad en el tiempo mayor o igual y
00:12:17
menor o igual
00:12:20
para resumir que es la notación
00:12:23
asintótica una forma de clasificar
00:12:26
algoritmos de cinco maneras
00:12:29
nivel como el crecimiento mayor a la
00:12:32
complejidad bic
00:12:34
como el crecimiento mayor o igual a la
00:12:36
complejidad
00:12:38
vez era como el crecimiento igual a la
00:12:41
complejidad
00:12:42
big omega como el crecimiento menor o
00:12:45
igual a la complejidad libro o mega como
00:12:49
el crecimiento menor a la complejidad
00:12:52
cada una cuenta con sus propias reglas o
00:12:55
condiciones de funcionamiento
00:12:59
dentro de esas reglas nos encontramos
00:13:02
con dos constantes c y n 0 donde se nos
00:13:05
invita a cumplir con la función de
00:13:07
crecimiento de cada anotación y n sub
00:13:10
zero nos define el valor mínimo desde
00:13:13
donde se cumple la condición para todos
00:13:15
los números n
00:13:17
genial vamos a la definición formal la
00:13:20
complejidad temporal puede ser
00:13:21
clasificada como notación asintótica la
00:13:24
cual se escribe como una función de
00:13:26
crecimiento g si y sólo si ya que
00:13:29
empezamos a declarar la regla dentro de
00:13:31
la notación existe una constante
00:13:33
positiva que multiplicada por el
00:13:35
crecimiento es mayor o igual que la
00:13:39
complejidad para todo n mayor a n sub
00:13:42
zero o dicho de otra forma desde un
00:13:44
punto en azul 0 para todos los números
00:13:47
en adelante la misma estructura de
00:13:49
definición se repite por ejemplo
00:13:51
convencerá de un algoritmo la
00:13:54
complejidad temporal puede ser
00:13:55
clasificada como anotación asintótica la
00:13:58
cual se escribe como una función de
00:14:00
crecimiento g si y sólo si existen dos
00:14:04
constantes positivas que multiplicadas
00:14:06
por el crecimiento son mayor o igual y
00:14:10
menor o igual que la complejidad
00:14:12
temporal para todos los números n mayor
00:14:15
a n sub zero
00:14:17
las notaciones asintóticas no solamente
00:14:20
se usan para representar el tamaño del
00:14:22
tiempo sino también del espacio como en
00:14:24
lugar de calcular segundos o minutos
00:14:26
calculamos kilobytes en memoria que son
00:14:28
ocupados cuando el tamaño de los datos
00:14:30
aumenta pero en realidad no cambia nada
00:14:33
en lo que respecta a lo que hemos visto
00:14:35
básicamente el sentido de estas
00:14:36
notaciones no cambia si se trata de
00:14:38
tiempo o espacio y esta es la notación
00:14:41
asintótica ahora que has comprendido
00:14:43
cómo funciona por dentro podemos hablar
00:14:46
también de cómo la calculamos en un
00:14:47
próximo vídeo espero te ha encantado
00:14:50
este vídeo muchas gracias por ver
00:14:52
[Música]
