Materia: #técnicas_y_diseños_de_algoritmos

Tags:

Computadora ideal

En Ciencias de la Computación llamamos problema a la descripción de lo datos de entrada y la respuesta a proporcionar para cada dato de entrada. Una instancia de un problema es un juego válido de entrada.

Vamos a suponer una máquina RAM, que está dada por una sucesión de celdas numeradas. Cada celda puede almacenar un valor de b bits. En general, el valor de b está fijo, y cada dato individual que maneja el algoritmo se almacena en b bits. Existe un programa imperativo que no se encuentra en la memoria, donde va a estar descripto nuestro algoritmo que resuelve el problema. Las asignaciones pueden acceder a celdas de memoria, aparte de acceder a operaciones estándar sobre los tipos de datos primitivos habituales.

En el apartado de complejidad esta explicado mas a fondo, pero vamos a retomar los cálculos de aproximaciones asintóticas. A su vez, vamos a incluir los cálculos para complejidad espacial, ya que las operaciones entre enteros o reales dependen de $b$. Las sumas y restas toman $O(b)$, mientras que multiplicar o dividir consiste en $O(b\log b)$. Como siempre, si $b$ se encuentra fijo, las complejidades se reducen a $O(1)$.

Para simplificar un poco esto, empleemos notación. Si tenemos una instancia $I$, definimos $|I|$ como el tamaño de dicha entrada, es decir, la cantidad de bits necesarios para almacenarlos en nuestra memoria. En otras palabras, $|I|=bn=O(bn)$, pero si suponemos $b$ fijo, resulta en $O(n)$.

Vamos a considerar satisfactorios aquellos algoritmos que tengan complejidad polinomial (cuanto menor sea el grado, mejor). Por otro lado, los algoritmos supra-polinomiales (los exponenciales, por ejemplo) van a ser considerados negativos.