Disculpas por la pregunta de novato, pero estoy un poco confundido acerca de lo que cuenta exactamente como una "operación simple" al calcular la complejidad temporal de un algoritmo. En particular, ¿por qué consideramos que todas las operaciones son iguales?
Seguramente, dividir dos números muy grandes lleva más tiempo que agregar uno a un número (como en cada iteración de un bucle for). La multiplicación, por ejemplo, puede consistir en cualquier cantidad de pequeñas adiciones. Entonces, en lugar de sumarlos, ¿no deberíamos aplicar algún tipo de peso a cada operación dependiendo del tipo de operación (suma, multiplicación, etc.) y el tamaño de los números involucrados?
Mi problema es que se me pide que demuestre que la complejidad de mi algoritmo es (para alguna función ) y no estoy seguro de cómo hacerlo matemáticamente riguroso debido a la vaguedad inherente en la definición de Una "operación simple". Entonces, ¿cómo voy a hacer esto?
fuente
Respuestas:
Las operaciones simples son todo lo que lleva tiempo constante para lograr. La confusión es que la división no parece tomar un tiempo constante, y de hecho, en general, no lo hace. ¡PERO!
La división y la suma toman tiempo constante si, por ejemplo, estás agregando dos enteros de 32 bits, que generalmente es así. Sin embargo, si está agregando números arbitrariamente grandes, en realidad no serán de tiempo constante, aunque a veces creo que la gente lo tratará como si fuera porque se supone que los números no son muy grandes.
fuente