La complejidad de una operación es básicamente cómo los recursos requeridos por la operación escalan en función de la entrada a la operación. Estos recursos pueden ser cualquier cosa en general, pero generalmente hablamos de complejidades espaciales y temporales. Además, generalmente nos preocupa la complejidad del peor de los casos, ya que luego obtenemos un límite superior en la cantidad de recursos que esperamos asignar para cualquier operación.
Volvamos a su pregunta ahora y supongamos que pregunta sobre la complejidad del tiempo. Vamos a nombrar la operación en cuestión como Op. Ahora, Op comprenderá varias operaciones básicas, como sumar, restar, multiplicar, asignar, etc. Podemos suponer que todas estas operaciones toman tiempo constante. Tenga en cuenta que esto no sucede en general, ej. – la suma de dos números de N bits lleva un tiempo proporcional al número de bits – Sin embargo, las computadoras representan números en formatos de longitud fija (los enteros se representan como 32 bits en C) y, por lo tanto, su suma, o cualquier otra operación básica para el caso, toma tiempo constante
Cuando medimos la complejidad del tiempo, en realidad no estamos estimando la escala del tiempo real que se requiere para el algoritmo. Ese es el rendimiento, no la complejidad, y depende de la máquina. Lo que realmente queremos es una estimación de cómo se escala el número de estas operaciones básicas con el tamaño de entrada.
- Cómo formular matemáticamente para seleccionar los mejores valores de N de una matriz
- Cómo interpretar 'lift' y 'odds ratio' en las reglas de asociación
- Si el universo es una simulación, ¿no estaría sujeto al problema de detención?
- Cómo entender el concepto de que 'si p entonces q' es equivalente a 'no p o q' Eg; 'Si muero, entonces me voy' es equivalente a 'Vivo o me voy'
- ¿Qué es mejor, una licenciatura con honores conjuntos en matemáticas / CS o matemáticas / física?
Entonces, para estimar la complejidad temporal de Op, debe dividirlo en bloques de operaciones básicas. Tenga en cuenta que si se realizan 10 (o cualquier número constante de) operaciones básicas en orden, entonces todas ellas constituirán un tiempo constante, lo que he denominado como un bloque. Luego, verifique el número de veces que se ejecuta cada bloque en el peor de los casos, y agregue todas las complejidades de los bloques individuales. Asegúrese de generalizar el tamaño de entrada de la entrada al hacer todo esto, es decir, en términos de, por ejemplo, N , que es una variable. Esto debería darle un peor caso relacionado con su operación.
Asegúrese de revisar la notación grande-Oh si aún no lo ha hecho. Además, la práctica facilitará todo esto.
