La complejidad de cualquier algoritmo le indica cuántos recursos utilizará la ejecución en algún tamaño de entrada n.
La complejidad del tiempo se puede ver como la medida de qué tan rápido o lento funcionará un algoritmo para el tamaño de entrada. La complejidad del tiempo siempre se da con respecto a algún tamaño de entrada (digamos n). Aquí hay un ejemplo para borrar el texto:
11 personas están paradas en una fila en orden ascendente con respecto a sus alturas. Ahora se le pide que informe a la mediana de sus alturas. Tienes 2 métodos para hacerlo:
- ¿Cuál es la diferencia entre analizar un archivo CSV y JSON? ¿Qué algoritmos comunes usarías en ambos?
- Cómo encontrar la menor supercadena de 2 subcadenas
- Una computadora pequeña tiene 4 marcos de página. Un proceso hace la siguiente lista de referencias de página; 1,2,3,4,1,5,2,3,1,2. ¿Cuántas fallas de página ocurren usando los siguientes algoritmos de reemplazo de página?
- ¿Pueden los algoritmos de aprendizaje de refuerzo actuales elegir múltiples acciones dado el estado actual?
- ¿Es bueno analizar?
- A partir de la primera persona (la más pequeña), registra la altura de cada persona en la línea y luego calcula la mediana de los datos. Observe que, en este método, pedimos (calcule) las alturas de los 11 hombres. Eso significa que hicimos el trabajo que se nos dio en el orden del total de hombres parados en la fila. ¿Y si hubiera n hombres? entonces nuestro cálculo habría sido n. Entonces podemos decir que la complejidad del tiempo está directamente relacionada con n u O (n).
- Actúas inteligentemente esta vez. Sabías que todos están parados en orden ascendente, por lo que no es necesario que vayan a cada persona. Luego vas a la persona parada en la sexta posición y le preguntas su altura. Él te dice su altura y tú declaras la respuesta. En este enfoque, no importaba si había 10 o 100 hombres, simplemente iría a la persona intermedia y obtendría la respuesta. Así que aquí tuvo que trabajar solo una vez, o podemos decir que la complejidad del tiempo es independiente del tamaño de entrada y puede escribirse como O (1).
Entonces, ¿qué método preferirías? Claramente el segundo.
La complejidad del espacio puede verse como la cantidad de memoria adicional que necesita para ejecutar su algoritmo. Al igual que la complejidad del tiempo, también se proporciona con respecto a algún tamaño de entrada (n). Otro ejemplo :
Se deben transportar 10 bolsas de un sitio a otro. De nuevo tienes dos opciones.
- Usted elige un vehículo pequeño que tiene un solo asiento y no puede mantener más de una bolsa en el asiento. Entonces tomas una bolsa y la transportas. Realiza 10 viajes (complejidad de tiempo) pero solo un asiento (complejidad de espacio). Del mismo modo, si tenía n bolsas y tiene la intención de transportarlas con el mismo medio, también necesitará un solo asiento. Por lo tanto, puede decir que la complejidad del espacio para esta solución será constante o independiente del tamaño de entrada (número de bolsas) u O (1).
- Ahora estaba harto de hacer muchos viajes entre los dos sitios. Usted elige un autobús con exactamente los mismos asientos que el número de maletas. Mantiene una bolsa por asiento en el autobús. Aquí, tenemos que hacer un solo viaje (complejidad de tiempo) pero hemos usado 10 asientos (complejidad de espacio). Aquí puede decir que el número de asientos (memoria adicional) es directamente proporcional al tamaño de entrada (número de bolsas). Entonces la complejidad del espacio es O (n).
Puede observar el intercambio espacio-tiempo en este ejemplo.
Nota: Hay muchas anotaciones para especificar la complejidad de un algoritmo, aquí he usado el límite superior o la notación Big Oh.
