¿Cómo puedo encontrar la complejidad temporal para un “bucle while” y una “sentencia de potencia”?
Estoy tratando de encontrar la complejidad temporal de dos declaraciones en Python:
1. Bucles while: Entiendo cómo encontrar la clase de complejidad de los bucles for, pero en el caso de los bucles while es completamente diferente, ¿cómo puedo detenerme aquí? la condición controla el bucle…
2. Declaración de potencia: ¿se ve afectada la complejidad temporal por la función pow?
Aquí tienes un ejemplo de una declaración en un programa:
Upper=100
n =random.randrange(0, Upper)
while gcd(n, Upper) != 1:
n = random. randrange(0, Upper) # pregunta 1
pow(c, n – 1, n) # (c ^n-1 mod n) pregunta 2
#donde n es un número primo grande
davy.ai
Complejidad temporal de los bucles while:
Cuando se trata de bucles while, la complejidad temporal se determina por el número de iteraciones necesarias para cumplir con la condición del bucle. En el ejemplo anterior, la condición del bucle while se verifica llamando a la función gcd hasta que se cumple la condición gcd(n, Upper) != 1. El número de iteraciones necesarias para cumplir esta condición depende de los valores de n y Upper. Por lo tanto, la complejidad temporal de este bucle while no se puede determinar sin conocer los valores de n y Upper.
Declaración de potencia y función pow:
La complejidad temporal de la función pow en la declaración de potencia depende del algoritmo utilizado para realizar la exponenciación modular. En general, la función pow utiliza el algoritmo de exponenciación binaria, que tiene una complejidad temporal de O(logn) donde n es el exponente. Este algoritmo es muy eficiente para exponentes grandes y reduce el número de operaciones de multiplicación necesarias. Por lo tanto, la función pow no afecta significativamente la complejidad temporal de la declaración de potencia. Sin embargo, si se utiliza un algoritmo diferente, la complejidad temporal puede ser diferente.