Complejidad: Algo de su teoría

Del origen del nombre del blog: https://es.wikipedia.org/wiki/Robot_de_Leonardo https://www.muyinteresante.es/historia/61295.html https://www.leonardo3.net/leonardo/books%20I%20robot%20di%20Leonardo%20-%20Taddei%20Mario%20-%20english%20Leonardo%20robots%201.html La teoría de complejidad intenta medir la ejecución de los programas de computadora desde dos puntos de vista del consumo de recursos: a) De los recursos de espacio, y b) de los recursos de tiempo. Una notación conocida como "O grande" es útil para describir cómo se comporta un programa asintóticamente (conforme la entrada consumida por el programa se hace mayor y mayor, en alguna medida). O(n) son los mejores programas que podemos tener como humanos (y sus primos O(log(n)) y O(n log(n)). Programas que involucran O(n**2), O(n**3)... ya no nos son tan buenos. Programas que involucran O(2**n), O(3**n)... ya nos son, para la práctica robótica, ajenos. Ejemplo de factorial recursivo (O(n) tiempo, O(n) espacio) Ejemplo de factorial iterativo (bien programado) (O(n) tiempo, O(k) espacio ---espacio acotado por una constante k, k>0) Ejemplo de programa O(n*log(n)) en consumo de tiempo: quick sort (ordenamiento rápido): def qs(ls): if len(ls)==0 or len(ls)==1: return ls else: a=ls.pop() ns=[x for x in ls if x>=a] ms=[x for x in lis if x