No entiende bien que significa el Big O. Alguien me da una mano?

El Big-O notation es una de esas cosas que nadie te sabe explicar que es pero que todos hablan de ello. Pero yo te lo explico, tu tranqui. . El Big-O notation lo que quiere decir es cuanto tiempo tarda un programa en terminar. En otras palabras, que tan rapido o que tan lento es. . . En la imagen de arriba podemos ver que tiene como base 2 parametros (el tamaño del input y el tiempo que tarda en ejecutarse el programa). El O(n^2) significa que entre mas grande el input, mas tardado el programa. El O(n) es completamente lineal, lo que significa que entre mas grande el input, mas tardado el programa. El O(log n) es acerca del logaritmo natural del tamaño del input. Por ultimo el O(1) es lineal, lo que significa que no importa el tamaño del input, siempre se va a tardar lo mismo el programa en correr

Añadiendo al comentario de @irvingjuarez he de decir que las n dentro de la O, tienen mucho sentido. Te doy un ejemplo. Imaginemos que tenemos una lista con n números (n puede ser el valor que nosotros queramos, 10 números, 100 números, o 1 billón), y queremos encontrar un numero concreto dentro de esa lista: La forma más natural, si es una lista desordenada, es ir uno a uno hasta encontrar el elemento que estabamos buscando, este algoritmo entonces tendria una O(n). ¿La razón de que sea O(n)? Nosotros no sabemos el número de iteraciones que tenemos que hacer en esa lista hasta encontrar el número deseado, de hecho, puede que el número no esté en la lista, o también puede ser que esté en la primera posición de la lista, pero una cosa es segura, de media, lo más probable es que tengamos que recorrer al menos la mitad de la lista hasta encontrarlo, pero de máximo (y ahí está la palabra clave) tendremos que recorrer los n elementos de la lista, hasta encontrarlo. Te inserto un pseudocódigo del algoritmo del que hablo:

def busqueda (lista, elemento_a_buscar):
	for idx, elemento in enumerable(lista):
		if elemento == elemento_a_buscar:
			return idx
	return -1

Como ves este es el algoritmo de busqueda lineal y tiene una O(n) es decir lineal.

Lo importante de este ejemplo, es que te quedes que el numero de veces que se ejecutará el bucle for, crece de forma lineal al numero n, si n = 10, habrán como máximo 10 iteraciones, si hay 10000 habrán como máximo 10000 iteraciones.

Un ejemplo de algoritmo con O(1) sería algo tan sencillo como una comparación, por ejemplo

def son_iguales  (numero1, numero2):
	return numero1 == numero2

es un statement que da igual la entrada que tenga como argumento, nunca tardará más o menos.

Y un ejemplo de función O(n²) sería la del algoritmo de ordenación de un array, poco usado, pero que es muy útil para este tipo de ejemplos, llamado Bubble Sort, te recomiendo este enlace de wikipedia donde hay pseudocódigo enlace a wikipedia. Lo más importante pero, es que te quedes con el concepto de que aquí la n es el tamaño del array, y que si por ejemplo, el array tiene 100 elementos (n = 100), entonces el ordenador tendrá que hacer de máximo 100² = 10000 comparaciones para ordenar un array, y que hay que tener cuidado con algoritmos que puedan tener ratios de crecimiento más grandes, como los algoritmos con coste exponencial, que pueden hacer que los programas tarden miles de años en acabar.

Espero que te haya sido útil mi explicación.

Muchas gracias cracks!!! impecalble.

tenia la misma duda y esta respuesta es excelente muchas gracias

@irvingjuarez muchas gracias