Python de notación o grande
Funciones y métodos de Python
Michael Zippo
01.11.2021
Nota : si no ha leìdo nuestro artìculo sobre complejidad del tiempo , se recomienda comenzar allì. La segunda parte de esta serie asume que está familiarizado con diferentes valores posibles de Big O.
En nuestro primer artìculo sobre Big O Notation y complejidad del tiempo , hablamos de cuánto tiempo tarda el algoritmo en completarse cuando aumenta su entrada. Esto es importante cuando interactuamos con conjuntos de datos muy grandes. Un gran conjunto de datos combinado con una complejidad de tiempo decente conduce a algoritmos más eficientes. Sin embargo, hay un aspecto más de la notaciòn Big O que debe tenerse en cuenta: la complejidad del espacio.
¿Qué es la complejidad del espacio?
La complejidad del tiempo y la complejidad del espacio son similares en lo que se relacionan con la cantidad de entrada que tiene un algoritmo. Cuando la complejidad del tiempo está relacionada con la cantidad de operaciones que un algoritmo necesita realizar para terminar, la complejidad del espacio está relacionada con la cantidad total de espacio necesaria para completar el algoritmo. La complejidad del espacio se expresa en términos de notaciòn Big O. & nbsp;
La complejidad del espacio incluye la cantidad de espacio necesario para la entrada, asì como el espacio auxiliar necesario en el algoritmo para ejecutarse. El espacio auxiliar es el espacio adicional utilizado para almacenar estructuras de datos temporales o variables utilizadas para resolver el algoritmo. Al igual que en la complejidad del tiempo, el Big O de un algoritmo considera el peor de los casos, o el lìmite superior asintòtico.
Averiguar el espacio requerido para ejecutar un algoritmo
Cuando calculamos Fuera de la complejidad espacial de un algoritmo, observe dos cosas: el tama√±o de entrada y el espacio auxiliar necesario para ejecutar la funciòn. En la mayorìa de los casos, no reducimos el tama√±o a la cantidad de bytes que tiene la entrada y ndash; solo miramos la cantidad de memoria que el espacio de entrada o auxiliar necesita usar. & nbsp;
La entrada de un algoritmo es lo que se pasa a la funciòn cuando se invoca. Por lo general, será una especie de valor primitivo: cadena, n√∫mero u objeto. El tama√±o exacto de cada uno puede diferir basado en el lenguaje, pero podemos calcular en un sentido general cuánto espacio se necesita.
Ejemplo con entradas y salidas simples
( Nota : Estamos usando Java aquì para que pueda discernir fácilmente los tipos de datos, pero esto puede aplicarse prácticamente a cualquier idioma.
Tome la funciòn anterior. El propòsito de esta funciòn es tomar una entrada & ndash; en en este caso, dos ints (abreviatura de enteros) y devuelven un resultado, también un int. & nbsp;
El 81% de los participantes declararon que se sentìan m Están seguros de sus perspectivas laborales en tecnologìa después de asistir a un campamento de entrenamiento. Asòciese a un bootcamp hoy.
El graduado promedio de un bootcamp pasò menos de seis meses en la transiciòn profesional, desde comenzar un bootcamp hasta encontrar su primer trabajo.
En nuestra opiniòn, tenemos dos variables & ndash; int a e int b. Nuestro valor devuelto & ndash; un int & ndash; también ocupa espacio. Debido a que nuestros n√∫meros enteros solo se eval√∫an una vez, consideramos que la complejidad del espacio aquì es O (1) & ndash; tiempo constante.
Ejemplo con entrada más compleja
Esta funciòn tiene una matriz como entrada. La matriz, sin conocer la longitud, tiene n ìndices. Las dos variables en las dos primeras lìneas de la funciòn son O (1) ya que se eval√∫an solo una vez. La suma es un n√∫mero entero, también es O (1). La gran O para la complejidad del espacio es O (n) para dictar el espacio para la matriz. & Nbsp;
Conclusiòn
El algoritmo más eficiente es el que toma la menor cantidad de tiempo y memoria. Sin embargo, será casi imposible, si no imposible, escribir un algoritmo que pueda satisfacer ambas condiciones. En √∫ltima instancia, tienes que sacrificar uno por el otro. La pregunta es, ¿cuál sacrificas?
La respuesta es: depende. Todo depende de los requisitos del proyecto o algoritmo en el que esté trabajando. Si solo tiene una memoria mìnima, debe sacrificar la complejidad del tiempo para usar el menor espacio y viceversa .
