Notacion Big O Algoritmos

Notación BIG O
Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas. Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo secomportarán cuando las implementemos, especialmente al atacar problemas "grandes".
El análisis de complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. Este "análisis de complejidad" intenta caracterizar la relación entre el número deelementos de datos y el uso de recursos (tiempo o espacio) con una aproximación matemática a través de una formula.
Ahora bien para calcular la complejidad de nuestros algoritmos tenemos nuestra notación BIG O. En esta tarea trataremos de dar una explicación concreta y sencilla de lo que es la Notación BIG O desde un enfoque de la Ciencia de la Computación.
¿Qué es la notación BIG O?
BIG O se utilizaen informática para describir el desempeño o la complejidad de un algoritmo. Big O describe específicamente el peor de los casos, y se puede utilizar para describir el tiempo de ejecución requerido por un algoritmo. Dentro de nuestra notación BIG O podemos encontrar 3 características principales que son fácilmente descritas a través de las siguientes palabras:
* Relativa: Únicamente puedescomparar manzanas con manzanas. No puedes comparar un algoritmo que hace multiplicación aritmética con uno que ordena una lista de enteros. No obstante, [comparar] dos algoritmos que hacen operaciones aritméticas (uno multiplicación y otro suma) te dirá algo significativo.
* Representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos a una única variable. Esa variablees elegida basándose en observaciones y supuestos. Por ejemplo, los algoritmos para ordenar son típicamente comparados en base a operaciones de comparación (comparar dos nodos para determinar su orden relativo).
* Complejidad: Si me toma un segundo ordenar 10.000 elementos, ¿cuánto me llevará ordenar un millón? La complejidad, en esta instancia, es una medida relativa de algo más.

Existengran cantidad de problemas en cuanto a informática se refiere que se pueden resolver mediante un algoritmo. Para resolver cada problema, podemos obtener más de un algoritmo propio que lo solucione, sin embargo, siempre acude a nuestro pensamiento ¿Cuál de ellos es el mejor para resolverlo?. Sería conveniente poder aplicar algún tipo de "puntuación" a los algoritmos, y que cuanta más puntuaciónsacara un algoritmo, pues supondremos que es mejor. Eso en cierto modo lo podemos definir como complejidad.

Saber si un algoritmo es mejor que otro puede estudiarse desde dos puntos de vista: un algoritmo es mejor cuanto menos tarde en resolver un problema, o bien es tanto mejor cuanta menos memoria necesite.

A la idea del tiempo que consume un algoritmo para resolver un problema lellamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial.

La complejidad espacial, en general, tiene mucho menos interés. El tiempo es un recurso mucho más valioso que el espacio. (Esto lo podemos ver también en el mundo real: si tienes dinero puedes comprarte una casa más grande, pero no puedes comprarte unos cuantos años más de vida). Así quecuando hablamos de complejidad a secas, nos estamos refiriendo prácticamente siempre a complejidad temporal.

La complejidad de un algoritmo es un "valor", por así decirlo, que nos da una idea de cuánto va a tardar un algoritmo en resolver el problema para el que fue diseñado.
El tamaño si importa.
La idea que subyace tras el concepto de complejidad temporal de un algoritmo es, básicamente,...