Notaci_n_para_complejidad_computacional - Brigith Lojan

Vista previa del material en texto

Universidad Nacional de Loja
Ing. Ciencias Computacionales
Complejidad Computaciona
Notación para complejidad
computacional
Big Omega
Jhandry David Tocto Barreto
Jhandry.tocto@unl.edu.ec
1150210662
Alex Paul Viñamagua Villalta
alex.vinamagua@unl.edu.ec
1719155085
Brigith Antonela Lojan Cabrera
brigith.lojan@unl.edu.ec
1150040846
Gerardo Manuel Quizhpe Chocho
gerardo.quizhpe@unl.edu.ec
1106078833
Luis Daniel Cobos Arévalo
luis.cobos@unl.edu.ec
1150404984
Loja, Ecuador
Noviembre 2021
2
Índice general
1. Introducción 2
1.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Desarrollo 3
2.1. Complejidad algoŕıtmica . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Notación asintotica . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3. Big Omega . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4. Ejemplos Practicos de Big Omega . . . . . . . . . . . . . . . . . 7
2.5. Concluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Referencias 8
1
Caṕıtulo 1
Introducción
La complejidad algoŕıtmica es una medida de cuánto tardaŕıa un algoritmo
en completarse dada una entrada de tamaño n. Si un algoritmo tiene que esca-
lar, debe calcular el resultado dentro de un ĺımite de tiempo finito y práctico
incluso para valores grandes de n. Por esta razón, la complejidad se calcula
asintóticamente cuando n se acerca al infinito.
Big Omega es una forma de representar la complejidad algoŕıtmica, y éste
describe la función de complejidad del mejor caso de un algoritmo, también da
un ĺımite inferior en la complejidad del algoritmo. Por ejemplo, si la función
de complejidad del mejor caso de un algoritmo es Ω (g(n)) este ĺımite inferior
también se aplica a su complejidad en cada entrada.
1.1. Antecedentes
Es necesario saber la eficiencia de un algoritmo antes de que este sea im-
plementado, similar a que un panadero sepa cuántas donas puede hacer en un
dia, esto es necesario principalmente para solucionar las dudas que pueda tener
el cliente a la hora de que se le entregue el producto ya que necesariamente
preguntara que tan rápido y eficiente es el programa que está por comprar,
siendo la medición de cuánto tarda en ejecutarse la respuesta más simple pero
no siempre es necesaria la ejecución del algoritmo para determinar la eficiencia
del mismo, a través de la notación asintomática y la complejidad algoŕıtmica
podemos encasillar la eficiencia de un algoritmo en una escala general, esto se
hace aśı pues no se tiene la certeza de saber el tiempo que tarda en ejecutar 20
entradas o 800 con lo cual resulta más eficiente la implementación de este tipo
de notaciones para saber que algoritmo es más eficiente para ser implementado
en el programa final. (Nasar, 2016)
2
Caṕıtulo 2
Desarrollo
2.1. Complejidad algoŕıtmica
El análisis de complejidad de un algoritmo consiste en estimar el tiem-
po de ejecución que gastará para una entrada de tamaño n. Ordenar 64.000
datos tomará más tiempo que ordenar diez datos; además, el algoritmo de
ordenamiento utilizado puede tomar diferentes tiempos para ordenar dos se-
cuencias de entradas del mismo tamaño, dependiendo de cuan parcialmente
ordenados se encuentren. En general, el tiempo tomado por un algoritmo cre-
ce con el tamaño de la entrada, de modo que es común describir el tiempo
de ejecución de un algoritmo como una función del tamaño de su entrada.
El tiempo de ejecución de un algoritmo para una entrada en particular es el
número de operaciones primitivas o pasos que son ejecutados. Una instruc-
ción podŕıa tomar una cantidad de tiempo diferente que otra instrucción, pero
se asumirá que cada ejecución de la i-ésima instrucción toma un tiempo ci,
donde ci es una constante. Para el análisis de los algoritmos tratados en es-
te art́ıculo nos centraremos en el tiempo de ejecución para el peor caso, ya
que éste ofrece un ĺımite superior en tiempo de ejecución para cualquier en-
trada y nunca tomará un tiempo mayor. (Roberto Emilio Salas Ruiz, 2013)
3
La complejidad algoŕıtmica es considerada la medida universal de complejidad.
Sin embargo, no existe algoritmo efectivo que, para una cadena, el algoritmo
produzca el entero que corresponda a la longitud del programa más corto (la
mejor compresión posible) que genere la cadena como salida (el resultado se de-
be al problema de la detención de la máquinas de Turing). Lo que significa que
uno no puede medir con absoluta certeza la complejidad algoŕıtmica de una ca-
dena. El cálculo del valor aproximado de la complejidad de Kolmogorov, gracias
a algoritmos de compresión sin pérdida, hacen del concepto una herramienta
de gran utilidad usado en diversas aplicaciones. De hecho existen aplicaciones
de la teoŕıa de la complejidad algoŕıtmica que han resuelto problemas de clasi-
ficación de todo tipo de objetos, para estudiar la similitud de ciertos idiomas,
especies de animales, para detectar fraudes (por ejemplo, plagios) y caracterizar
imágenes.(Zenil, 2011)
2.2. Notación asintotica
En matemáticas la aśıntota es una ĺınea que continuamente se aproxima a
una curva dada pero nunca la cruza o intersecta. Lo más relevante en el uso
de la notación asintótica es para determinar la eficiencia de los algoritmos, es
decir, sirve para estimar matemáticamente la cantidad de recursos requeridos
en la ejecución de un programa.
Este tipo de notación se vuelve necesaria ya que no hay una computadora
estándar o máquina modelo ideal universal para ser tomada como referencia
para medir el tiempo de corrimiento de los algoritmos a usarse en programas
4
de computadora. El análisis de algoritmos también es una herramienta para los
diseñadores para estimar si una solución propuesta satisface las restricciones de
recursos de un problema. (Guadalajara, 2003). (B., 2003)
Notaciones asintóticas O (f ), Ω (f )y θ( f ).
Si f es una función de N en R, se denota por O (f (n)), o simplemente O(f ),
al conjunto de todas las funciones dominadas por f.
Formalmente O(f )= g — g: N →R es función y g ¡f .
Si una función g pertenece al conjunto O(f ) se escribe g ε(f ) y se suele decir
que “g es o mayúscula de f” o que “g es del orden de f” (aunque en la realidad
es la letra griega ómicron) . Si f es O(g) entonces O(g) es una cota superior de
f.
Si f y g son dos funciones de N en R, es decir, f: N→R y g: N→R, y además
existen k 0 y m 0 donde k, m εZ tales que para todo entero n m se verifica
la desigualdad —f(n)— k —g(n)—, entonces el conjunto de todas las funciones
que cumplan la condición anterior se denota con Ω (f) y se lee “f es omega de
g”. Si f es Ω (g) entonces Ω (g) es cota inferior de f.
Como [f ] representa un conjunto (el de todas las funciones equivalentes a
una función f ), se suele representar más comúnmente por Ω ( f ).
Si f es θ(f ) entonces θ(f ) es a la vez tanto una cota inferior como una
superior de f. Por lo que: θ( f )= O(g) Ω (g)
Formalmente se puede decir que si f y g son dos funciones de N en R, es
decir, f: NR y g: NR, y además existen k1 0, k2 0 y m 0 donde k1, k2, m
Z tales que para todo entero n m se verifica la desigualdad k1 —g(n)— —f
(n)— k2—g(n)l—, entonces el conjunto de todas las funciones que cumplan la
condición anterior se denota con (f) y se lee “f es theta de g” .
Puesto que ( f ) define una relación de equivalencia, se puede indicar la clase
de complejidad de un algoritmo especificando cualquier función de la clase. Por
lo regular se escoge el representante más sencillo. (José A. Cárdenas-Haro, 2013)
(Cárdenas-Haro, 2013)
5
2.3. Big Omega
Cuando se usa la notación Ω para describir la función de complejidad del
mejor caso de un algoritmo, también da un ĺımite inferior en la complejidad
del algoritmo. Por ejemplo, si la función de complejidad del mejor caso de un
algoritmo es Ω (g (n)) este ĺımite inferior también se aplica a su complejidad
en cada entrada. Con big-Theta, sin embargo, si encontramosque la función de
complejidad en el mejor de los casos de un algoritmo es θ(g (n)), esto no no
implica un ĺımite de θ(g (n)) en la complejidad del algoritmo para cada entrada.
Gran-Omega: Sean f (n) y g (n) dos funciones con valores positivos, decimos
que f (n) = Ω(g (n)), si hay una constante c tal que f (n) cg (n)) para todos
menos para un número finito n.
Si f (n) = Ω (g (n)) decimos ”f (n) es Ω (g (n))”. Una representación geométri-
ca de f (n) =Ω (g (n)) se puede ver en la siguiente figura. (Nasar, Audrey A)
Hay dos definiciones extendidas e incompatibles de esta notación, una es
introducida por Hardy–Littlewood y el otro de Knuth. En este caso se usa la
definición de Knuth que dice que esta función nos da un ĺımite inferior. Puede
leerse como ”pedir al menos f (n) ”(Atamazhori, Sam and Hassanvand, Arsalan
and Omidvar, Sepehr).(Atamazhori, Hassanvand, y Omidvar, 2021)
También podemos hacer afirmaciones correctas, pero imprecisas, al usar la
notación Ω grande. Por ejemplo, si en verdad tienes un millón de pesos en el
bolsillo, ciertamente podŕıas decir ”tengo una cantidad de dinero en mi bolsillo
y es por lo menos de 10 pesos”. Eso es correcto, pero ciertamente no muy
preciso. Del mismo modo, podemos decir de manera correcta pero imprecisa
que el tiempo de ejecución del peor caso de la búsqueda binaria es Ω (1) porque
sabemos que tarda por lo menos un tiempo constante. (Dartmouth Computer
Science Thomas Cormen y Devin Balkcom)
6
2.4. Ejemplos Practicos de Big Omega
El resultado de un analizador de costos estático suele ser una función que
asigna los valores de entrada al costo de las ejecuciones correspondientes. Dado
que el problema es claramente indecidible, Estas funciones no describen el costo
exacto sino más bien un ĺımite superior en el costo del peor de los casos o
un ĺımite inferior del costo del mejor de los casos. Pueden darse en una forma
asintótica y utilizando notaciones como Big O y Big Omega. Además,cuando
los datos de entrada no son numéricos, por ejemplo, una estructura de datos o
una matriz, los datos correspondientes se abstraen t́ıpicamente a alguna medida
numérica que se llama su tamaño, por ejemplo, el tamaño de una matriz, la
longitud de una lista, la profundidad de un árbol, etc. Al contar el número
de veces que se ejecuta la condición del bucle interno, El analizador de costos
devolveŕıa la función de ĺımite superior sort y la función de ĺımite inferior sort
(n) = n, donde n se refiere a la longitud de la matriz de entrada. Que podŕıa
también dar una forma asintótica como O (n2) en el peor de los casos y Ω (n)
en el mejor caso.
2.5. Concluciones
Para comprender la importancia de la Notación Asintótica, conviene resaltar
su valor dentro de las ciencias de la computación dentro de las cuales nos ayudan
a simplificar las funciones que representan la tasa de crecimiento de un algoritmo
permitiéndonos realizar una clasificación de los mismos.
Se dedujo que la notación Big Omega (Ω) es similar a Big O, ya que la
notación Big O nos proporciona un ĺımite superior asintótico en una función, y
la notación Big Omega(Ω) nos proporciona un ĺımite inferior asintótico, por lo
que se deberá ver cuál es la mejor solución al momento de aplicarlo en algún
ejercicio.
7
Referencias
Atamazhori, S., Hassanvand, A., y Omidvar, S. (2021). On asymptotic notation:
an introduction to analyses of algorithms.
B., J. F. V. (2003, 01 de Agosto). AnÁlisis asintÓtico con aplicaciÓn de
funciones de landau como mÉtodo de comprobaciÓn de eficiencia en al-
goritmos computacionales. Descargado de https://blogthinkbig.com/
ventajas-latex-editar-documentos
Cárdenas-Haro, J. A. (2013). La notación asintótica en el cómputo
cient́ıfico. Descargado de https://www.eumed.net/rev/tlatemoani/12/
algoritmo.pdf
Nasar, A. A. (2016). The history of algorithmic complexity. The Mathematics
Enthusiast , 13 (3), 217–242.
Roberto Emilio Salas Ruiz, J. E. R. R. (2013, 08 de Julio). Vista de anÁlisis de
complejidad algorÍtmica. Descargado de https://revistas.udistrital
.edu.co/index.php/vinculos/article/view/4071/5739
Zenil, H. (2011, 26 de Agosto). Un metodo estable para la evaluacion de la
complejidad algoritmica de cadenas cortas. Descargado de https://arxiv
.org/abs/1108.5387
8
https://blogthinkbig.com/ventajas-latex-editar-documentos
https://blogthinkbig.com/ventajas-latex-editar-documentos
https://www.eumed.net/rev/tlatemoani/12/algoritmo.pdf
https://www.eumed.net/rev/tlatemoani/12/algoritmo.pdf
https://revistas.udistrital.edu.co/index.php/vinculos/article/view/4071/5739
https://revistas.udistrital.edu.co/index.php/vinculos/article/view/4071/5739
https://arxiv.org/abs/1108.5387
https://arxiv.org/abs/1108.5387
	Introducción
	Antecedentes
	Desarrollo
	Complejidad algorítmica
	Notación asintotica
	Big Omega
	Ejemplos Practicos de Big Omega
	Concluciones
	Referencias