2 de mayo de 2018
La notación de la \(O\) mayúscula (big O notation) es una construcción matemática que nos permite, a grandes rasgos, describir el comportamiento de una función en su limite.
Es miembro de la familia de notaciones conocidas como notaciones de Bachmann-Landau o notaciones asintóticas.
Otros miembros de la familia de notaciones asintóticas son las notaciones \(o\), \(\Omega\) y \(\theta\).
En geometría analítica, una asíntota es una linea que delimita el comportamiento de una función en su límite.
Esto es, la distancia entre la función y la linea delimitadora tienden a cero.
Formalmente, \(O\) se define como:
Sean \(f\) y \(g\) dos funciones con dominio en los números reales positivos. Tenemos que \[f(x)=O(g(x)),\] o de forma alternativa \[f(x) \in O(g(x)),\] si y sólo si
\[\limsup_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| < \infty.\]
Una caracterización equivalente de \(O\) es:
\(f(x)=O(g(x))\) si y sólo si:
Sean \(f(x)=3x + 10\) y \(g(x)=x\). ¿Es \(f\) del orden de \(g\)?
Sea \(M=10\), notemos que \[f(x) = 3x + 10\leq 10x = 10g(x)\] para toda \(x \geq 2\): \(f(2)=16\) y \(10g(2)=20\).
Sigue que \(f(2)\leq 10g(2)\) y la desigualdad crece con \(x\).
\[\limsup_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| =\lim_{x\to\infty} \left| \frac{ 3x + 10}{x} \right| = 13 < \infty.\]
Por lo tanto, \(3x+10\) es del orden de \(x\).
Sean \(f(x)=x^2+50x+1\) y \(g(x)=x^3-100\).
¿Es \(f\) del orden de \(g\)?
Método dos:
\[\limsup_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| = \lim_ {x\to\infty} \left| \frac{x^2+50x+1}{x^3-10}\right| \]
Por L'Hospital:
\[\lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| = \lim_{x\to\infty} \left| \frac{f'(x)}{g'(x)} \right|,\] de donde
\[ \lim_{x\to\infty} \left| \frac{f'(x)}{g'(x)} \right| = \lim_{x\to\infty} \left| \frac{2x+50}{3x^2} \right| =\lim_{x\to\infty} \left| \frac{2}{6x} \right|=0 < \infty.\]
Por lo tanto, \(x^2+50x+1= O(x^3-100)\).
Sean \(f(x)=x^{100}\) y \(g(x)=1.00001^{x}\).
¿Es \(f\) del orden de \(g\)?
\[ \lim_{x\to\infty} \left| \frac{f'(x)}{g'(x)} \right| = \lim_{x\to\infty} \left| \frac{100 x^{99}}{9.99995\times{}10^{-6}\times 1.00001^x} \right|\]
y, en general, para 99 derivadas vamos a tener:
\[ \lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| = \lim_{x\to\infty} \left| \frac{\alpha\beta x^{\beta-1}}{9.99995\times{}10^{-6}\gamma 1.00001^x} \right|,\] con \(\beta\) decreciente y eventualmente 0. Sigue que el limite es 0.
Sigue que \(f\) es del orden de \(g\).
Sean \(f(x)=x^{2}+5000\) y \(g(x)={x^2}-5000\).
¿Es \(f\) del orden de \(g\)?
\[ \lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| =\left| \frac{f'(x)}{g'(x)} \right| =\left| \frac{2x}{2x} \right| = 1 < \infty.\] De donde \(f\) es del orden de \(g\).
Sean \(f(x)=10^{100}x^{3}\) y \(g(x)=0.0001{x^3}\).
¿Es \(f\) del orden de \(g\)?
Sean \(f(x)=10^{100}x^{3}\) y \(g(x)=0.0001{x^3}\).
¿Es \(f\) del orden de \(g\)?
\[ \lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| = \left| \frac{10^{100}{x^3}}{0.0001x^{3}} \right| = \frac{10^{100}}{0.0001} < \infty.\]
Por lo tanto \(f\) es del orden de \(g\).
Sean \(f(x)= \log_2 x\) y \(g(x)= \log_{10}x\).
¿Es \(f\) del orden de \(g\)?
Sean \(f(x)= \log_2 x\) y \(g(x)= \log_{10}x\).
¿Es \(f\) del orden de \(g\)?
Notemos que: \[\begin{align} 2^{\log_2 x} &= x\\ log_{10}(2^{\log_2 x}) &= \log_{10} x\\ (\log_2 x) \log_{10}(2) &= \log_{10} x\\ \end{align}\]
de donde para toda x > 0: \[(\log_2 x) \leq \frac{1}{\log_{10}(2)} \log_{10} x.\]
Sean \(f(x)= 2.1^x\) y \(g(x)= 2^x\).
¿Es \(f\) del orden de \(g\)?
Sean \(f(x)= 2.1^x\) y \(g(x)= 2^x\).
¿Es \(f\) del orden de \(g\)?
\[ \lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| = \lim_{x\to\infty} \left| \frac{2.1^x}{2^x} \right| = \lim_{x\to\infty} \left(\frac{2.1}{2} \right)^x = \infty.\]
Por lo tanto \(f\) no es del orden de \(g\).
Si \(f(n) = O(g(n))\) pero \(g(n) \neq O(f(n))\) entonces decimos que \(g\) es de mayor orden (crece más rápido) que \(f\).
Si \(f(n) = O(g(n))\) y \(g(n) = O(f(n))\) entonces decimos que \(g\) y \(f\) tienen el mismo orden.
¿Cuál de las siguientes funciones es de mayor orden?
Si \(f\) puede ser escrita como una suma finita de otras funciones, aquella que crece más rápido determina el orden de \(f(n)\).
Si \(f\) puede ser escrita como una suma finita de otras funciones, aquella que crece más rápido determina el orden de \(f(n)\).
Producto: Si \(f_1(n) = O(g_1(n))\) y \(f_2(n) = O(g_2(n))\) entonces \[f_1(n)f_2(n) = O(g_1(n)g_2(n)).\]
Por ejemplo: \(O(2n\times3n^2) = O(6n^3)\).
Suma: Si \(f_1(n) = O(g_1(n))\) y \(f_2(n) = O(g_2(n))\) entonces \[f_1(n)+f_2(n) = O(g_1(n)+g_2(n)).\]
Por ejemplo: \(O(2n+3n^2) = O(3n^2)\).
Si \(C\) es una constante diferente de 0 entonces, para toda función \(f(n)\), \[O(Cf(n))=O(f(n))\] y \[O(f(n)+C)=O(f(n)).\]
Por ejemplo: \(O(3n^2) = O(n^2)\).
Para toda constante función constante \(f(n) = C\), \(C>0\), tenemos que \(f(n) = O(1)\).
No importa la base de los logaritmos: Sean \(f_1(n) = \log_{b_1}\) y \(f_1(n) = \log_{b_2}\), con \(b_1,b_2>1\), entonces \(f_1(n)\) y \(f_2(n)\) son del mismo orden.
"Machine with Concrete" por Arthur Ganson, http://arthurganson.com/project/machine-with-concrete/
Construida en 1992, el motor en el lado izquierdo gira a 200rpm mientras que el último engrane esta esta pegado a un bloque de concreto. Cada uno de los 12 engranes disminuye la velocidad de rotación en \(\frac{1}{50}\).
La velocidad de rotación del último engrane es de \[200\times{} \left( \frac{1}{50} \right) ^{12}\] rotaciones por minuto. Lo anterior equivale a una rotación cada \(4.306\times 10^{-13}\) años.
En otras palabras, ¡el último engrane realiza poco más de 4 rotaciones cada un 10 trillones de años!
Sea \(c\) una constante mayor a 1.
| Notación | Nombre |
|---|---|
| \(O(1)\) | orden constante |
| \(O(\log \log n)\) | orden sublogarítmico |
| \(O(\log n)\) | orden logarítmico |
| \(O(\sqrt{n})\) | orden sublineal |
| \(O(n)\) | orden lineal o de primer orden |
| \(O(n \log^* n)\) | \(n\) log-estrella \(n\) |
| Notación | Nombre |
|---|---|
| \(O(n \log n)\) | orden lineal logarítmico o quasilineal |
| \(O(n^2)\) | orden cuadrático o de segundo orden |
| \(O(n^3)\) | orden cúbica o de tercer orden, etc. |
| \(O(n^c)\) | orden polinomial o algebraico |
| \(O(c^n)\) | orden exponencial |
| \(O(n!)\) | orden factorial |
Un parámetro primordial durante el desarrollo de proyectos de software es el poder controlar los recursos computacionales que un programa o sistema va ha utilizar durante su ejecución.
Para el análisis de algoritmos y la teoría de la complejidad computacional, los recursos más importantes son el tiempo y la memoria requeridas para la ejecución de un programa.
La notación \(O\) es usada para la clasificación de algoritmos ya que esta es robusta (depende poco) con respecto a diferencias de implementación así como del hardware disponible:
En general, los ordenes de ejecución se mantienen bajo diferencias en lenguaje de programación, habilidad del programador y diferencias de hardware.
La variable \(n\) representa el tamaño de la entrada tanto en bits, bytes, palabras o números de elementos de un problema de tamaño acotado, no importa cuál se use ya que, por la propiedad multiplicativa, el orden no va ha cambiar.
Para un algoritmo de ordenación como merge sort, \(n\) es el número de elementos a ordenar ya que, normalmente, estos van a ser de un tamaño fijo en bits.
En general, en el análisis de algoritmos y la teoría de la complejidad vamos a considerar los recursos usados por un algoritmo en tres casos distintos:
De estos, los últimos dos son considerados los más importantes.
El mejor caso es el desempeño de un algoritmo en condiciones ideales.
En términos informales, el caso promedio es aquel que se espera encontrar en la mayoría de las veces.
En términos informales, es el peor caso se da en las entradas donde el algoritmo tiene el desempeño más lento.
El determinar estos casos no es trivial y frecuentemente requiere conocimientos avanzados de análisis de algoritmos y probabilidad.
Son medidas estándares en la industria.
Normalmente se requiere dar la información para ambos casos cuando se especifica el desempeño de un algoritmo.
Es muy recomendable establecer que tan frecuentemente se esperan los peores casos.
Es muy controversial el preferir un caso sobre el otro para determinar el desempeño de un algoritmo.
def insertionSort_time(n_lista):
for index in range(1,len(n_lista)):
actual = n_lista[index]
posicion = index
while posicion>0 and n_lista[posicion-1]>actual:
n_lista[posicion]=n_lista[posicion-1]
posicion = posicion-1
n_lista[posicion]=actual
return n_lista
def quicksort_time(lista):
quicksort_aux(lista,0,len(lista)-1)
def quicksort_aux(lista,inicio, fin):
if inicio < fin:
pivote = particion_time(lista,inicio,fin)
quicksort_aux(lista, inicio, pivote-1)
quicksort_aux(lista, pivote+1, fin)
def particion_time(lista, inicio, fin):
pivote = lista[inicio]
izquierda = inicio+1
derecha = fin
bandera = False
while not bandera:
while izquierda <= derecha and lista[izquierda] <= pivote:
izquierda = izquierda + 1
while lista[derecha] >= pivote and derecha >=izquierda:
derecha = derecha -1
if derecha < izquierda:
bandera= True
else:
# swap places
temp=lista[izquierda]
lista[izquierda]=lista[derecha]
lista[derecha]=temp
# swap inicio with lista[derecha]
temp=lista[inicio]
lista[inicio]=lista[derecha]
lista[derecha]=temp
return derecha
def merge(ls, rs, acc):
if not ls:
acc.extend(rs)
return acc
if not rs:
acc.extend(ls)
return acc
l = ls[0]
r = rs[0]
if l < r :
ls.pop(0)
acc.append(l)
return (merge(ls, rs, acc))
else:
rs.pop(0)
acc.append(r)
return (merge(ls, rs, acc))
def mergeSort(lst):
if len(lst)==1 :
return lst
ls = lst[:len(lst)/2]
rs = lst[len(lst)/2:]
return(merge (mergeSort(ls),mergeSort(rs),[]))
Recuerden la práctica 12:
Desempeño sobre listas aleatorias
Recuerden la práctica 12:
Desempeño sobre listas ya ordenadas
1.- Encontrar las funciones y herramientas que el lenguaje y el sistema operativo ofrecen para medir el uso de recursos de un programa y el como usarlos.
time() en Python nos da el tiempo actual del sistema en segundos (y fracciones) como un número flotante. Al realizar el siguiente código:tiempoIni = time() # Proceso print(time() - tiempoIni)
Imprimimos en pantalla cuanto tardo, aproximadamente, en ejecutarse el código entre las líneas tiempoIni = time() y print(time() - tiempoIni).
2.- Obtener una muestra d entradas de distintos tipos y tamaños.
3.- Analizar los resultados.
El tiempo de ejecución se puede medir contando el número de accesos a memoria.
Sin embargo, es más común medir por pasos del programa: (Fuente: http://slideplayer.es/slide/3121639/)
if, else) cuenta como el número de pasos de la expresión que debe ser evaluada.return cuenta como el número de pasos de la expresión que debe ser evaluada.Sea \(n\) la longitud de la lista lista:
| Linea | Pasos | Accesos a memoria | Frecuencia | Total |
|---|---|---|---|---|
def sumatoria(lista): |
||||
s = 0 |
1 | 1 | 1 | 1 |
for i in lista: |
1 | 2 | \(n\) | \(n\) |
s = i + s |
1 | 3 | \(n\) | \(n\) |
return s |
1 | 1 | 1 | 1 |
Total Pasos = \(2n+2\)
Sea \(n\) la longitud de la lista lista:
| Linea | Pasos | Frecuencia | Total |
|---|---|---|---|
def dobleSumatoria(lista): |
|||
s = 0 |
1 | 1 | 1 |
for i in lista: |
1 | \(n\) | \(n\) |
for i in lista: |
1 | \(n^2\) | \(n^2\) |
s = i + s |
1 | \(n^2\) | \(n^2\) |
return s |
1 | 1 | 1 |
Total Pasos = \(2n^2 + n + 2\)
Es muchos casos, es posible el disminuir el tiempo de ejecución de un algoritmo al aumentar el espacio usado y viceversa. Este fenómeno se conoce como space-time o time-memory trade-off, compensación espacio y tiempo.
Los casos más comunes son:
Código compacto o loop unrolling.
Uso de tablas de búsqueda o recalcular los datos
Uso de datos comprimido o sin compresión.
Reproducción de imagines en tiempo real o almacenado.
Loop unrolling, desenrollado de ciclos, es el acto de expresar una operación recursiva linea por linea en lugar de usar un ciclo o una recursión.
Por ejemplo, en lugar de usar un ciclo for desde o hasta \(n-1\) usamos \(n \times m\) lineas de código expresando cada operación \(n\) veces.
Esa una opción de optimización muy común para los compiladores.
El usar un ciclo es más lento ya que tenemos que hacer todas las operaciones de comparación y asignación.
El usar un ciclo desenrollado usa más memoria ya que el programa en sí es más largo.
Visto por otro lado, podemos modificar un algoritmo que usa tablas para que estas se generen en el momento, requiriendo menos memoria pero a costo de mayor tiempo de cómputo.
Esta es una instancia de las técnicas conocidas como Memoización.
def fibonacci_recursivo(numero):
if numero == 1: #Caso base
return 0
if numero == 2 or numero == 3:
return 1
return fibonacci_recursivo(numero-1) + fibonacci_recursivo(numero-2)
memoria = {1:0, 2:1, 3:1}
def fibonacci_memo(numero):
#Si el número ya se encuentra calculado,
#se regresa el valor ya ya no se hacen más cálculos
if numero in memoria:
return memoria[numero]
memoria[numero] = fibonacci_memo(numero-1)
+ fibonacci_memo(numero-2)
return memoria[numero]
Notación \(o\) (\(o\) minúscula):
\[f(x)=o(g(x))\ \Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|= 0.\]
Notación \(\Omega\): \[f(n)=O(g(n)) \Leftrightarrow g(n) = \Omega(f(n)).\] \[f(x)=\Omega(g(x))\ \Leftrightarrow\;\liminf_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0.\]
Notación \(\Theta\):
\(f(n)= \Theta(g(n))\) si \(f(n)=O(g(n))\) y \(f(n)=\Omega (g(n))\).
Para esta sección del curso, los objetos de estudio van a ser problemas que, en principio, se pueden resolver por medio de un algoritmo. Este tipo de problemas con llamados problemas computables.
Ejemplos de problemas computables:
Encontrar la raíz cuadrada de un número.
Calcular el n-esimo dígito de \(\pi\).
Ordenar una lista finita.
Encontrar la ruta más corta entre dos direcciones.
Calcular la órbita aproximada del cometa Halley a partir de las observaciones disponibles y la teoría de gravitación de Newton.
La ciencias de la complejidad es la disciplina científica que se enfoca en catalogar y encontrar propiedades de objetos basados en su dificultad (para problemas) o su profundidad aparente.
En la teoría de la complejidad computacional, las clases de complejidad son una serie de problemas que se consideran equivalentes en el sentido de que ocupan la misma cantidad de recursos computacionales (tiempo o memoria).
Un problema se demuestra que pertenece a cierta clase de complejidad si el tener una solución a un problema perteneciente a esta clase nos ayuda a resolver el primer problema en un tiempo corto o espacio pequeño.
Los requerimientos de memoria y de tiempo se consideran por separado.
Hay cientos de clases de complejidad computacional. En este curso nos enfocaremos en tres clases: \(P\), \(NP\) y \(NP\text{-}C\).
La clasificación se hace en términos de la notación \(O\) mayúscula.
La relación entre algunas clases de complejidad
La clase \(PTIME\) o \(P\) se define como aquella que contiene a los problemas de decisión (si o no) que se pueden resolver en tiempo polinomial por una máquina de Turing. Una máquina de Turing es de tiempo polinomial si el número de transiciones en función del tamaño de la entrada es del orden \(O(n^c)\) para alguna \(c\geq1\) constante.
Ya que muchos problemas cotidianos se pueden replantear como problemas de decisión, vamos a definir de manera informal a esta clase como:
Vamos a llamar a esta clase como la clase de los problemas y algoritmos polinomiales.
Canónicamente, se considera que esta clase contiene a todos los problemas computacionales que se pueden resolver de manera efectiva, en otras palabras que son tratables.
Algunos problemas fundamentales en \(P\) son:
Comúnmente, la clase \(NP\) se interpreta como la clase de problemas que no se pueden resolver en tiempo polinomial. ESTA ES UNA INTERPRETACIÓN ERRÓNEA!
La definición correcta es: La clase \(NP\) es aquella que esta compuesta de problemas que se pueden resolver en tiempo polinomial por una máquina de Turing no determinista.
Esta definición incluye a todos los problemas en \(P\) y descarta a una infinidad de problemas que no se pueden resolver en tiempo polinomial.
Es equivalente a pedir que la respuesta se pueda verificar en tiempo polinomial dado un certificado.
El entender esta definición requiere conocimiento avanzado de máquinas de Turing que no es parte de este curso.
De manera informal, un problema esta en \(NP\)-Hard si es, al menos, tan difícil de resolver que el problema más difícil en \(NP\).
Para nuestros propósitos, podemos pensar en los problemas \(NP\)-Hard como una clase de problemas en \(NP\) que no son polinomiales.
Un problema es \(NP\)-\(C\) (\(NP\)-Completos) si es esta en \(NP\) y además es \(NP\)-Hard.
Una forma de pensar en los problemas \(NP\)-Completos es en un conjunto de problemas que se sospecha que no son polinomiales, pero no se a demostrado que lo son.
El resolver la pregunta \(NP=P\) o \(NP \neq P\) es considerada uno de los problemas sin resolver más importantes en la ciencia actualmente. Como recompeza a quien lo resuelva hay un premio de 1 millón de dolares, aunado a fama eterna.
Un problema es \(NP\)-\(C\) (\(NP\)-Completos) si es esta en \(NP\) y además es \(NP\)-Hard.
P vs NP
Y muchos más.
Existen varios métodos de intentar dar una solución buena a un problema NP-C. Entre estos se encuentran los Algoritmos "Greedy" o codiciosos.
Un algoritmo greedy (codicioso) es un algoritmo que fue diseñado bajo la heurística de dividir un problema en problemas más pequeños y obtener una solución óptima en estos, esperando que la solución conjunta sea buena.