1.2 Aritmetica Notacion

En general, el tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2)

Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el número de vértices de éste.

La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso.

A veces ocurre que no hay que prestar demasiada atención a esto. Conviene diferenciar entre el peor caso y el esperado. Por ejemplo, el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Sin embargo, en la práctica este caso no se da casi nunca y la mayoría de los casos son proporcionales a N•logN. Es por ello que se utiliza esta última expresión para este método de ordenación.

Un ejemplo sencillo es el siguiente:

Ejemplo
Al encender un auto en la mañana se tiene que dejar calentando por un buen tiempo para que no tenga problemas al andar por la calle es un tiempo de ejecución tardado pero es necesario para que no tengas perdida de tiempo mas adelante

Otro ejemplo es el tiempo de ejecución que se necesita para cargar un programa a la computadora el tiempo puede variar según el tamaño del programa

Una definición rigurosa de esta notación es la siguiente:

Una función g(N) pertenece a O(f(N)) si y sólo si existen las constantes c0 y N0 tales que:

|g(N)| ‹= |c0•f(N)| , para todo N ›= N0.

- Clasificación de problemas

Los problemas matemáticos se pueden dividir en primera instancia en dos grupos:

• Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.
• Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo.

Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solución, pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos:

• intratables: aquellos para los que no es factible obtener su solución.
• tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.

Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinomio que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejores algoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.