¿Cómo determino la complejidad temporal de una expresión matemática que involucra potencias, divisiones y exponenciales? Sé la complejidad temporal de las operaciones simples, pero no sé cómo se supone que las combino para encontrar la respuesta.

Por lo general, está tratando de encontrar la complejidad del tiempo de operaciones completas en números, eliminando todas las constantes e incluso tomando el término de crecimiento más rápido de una suma del costo real. Esto fue, cada operación es tiempo constante.

Sin embargo, si observa el número de operaciones en relación con el número de bits, o en relación con el valor numérico, cada operación tiene un costo diferente.

Por ejemplo,

Las operaciones en modo bit son tiempo constante en relación con el número de bits, porque todas pueden realizarse en paralelo.
La suma es lineal (tiempo de sumador medio) o tiempo logarítmico (transporte anticipado en lugar de tiempo de espera).
El cambio es lineal cuando se usa una tubería, o más probablemente constante cuando se usa una palanca de cambios de barril.
La multiplicación, cuando se realiza como sumar (llevar anticipación) y tamizar (desplazador de barril) es el número de bits de un multiplicando multiplicado por el costo de cada ciclo de adición.
La división es típicamente un número de bits de wrt lineal en el numerador.
La exponenciación de enteros es el costo de una sola multiplicación por [math] ceil (log_2 ([/ math] número de bits de exponente [math])) [/ math].
La descomposición primaria de fuerza bruta de un número [matemática] N [/ matemática] toma como máximo los pasos de división [matemática] \ sqrt {N} [/ matemática].

Por lo tanto, depende del algoritmo utilizado. En general, puede suponer que los mejores algoritmos posibles se implementan en el hardware, pero debe verificar la implementación del software siempre que sea posible.

Luego está la aritmética de gran número, que siempre se realiza en software, y generalmente puede mirar el código y verificar la complejidad usted mismo.

Algoritmoscomplejidadcomplejidad del tiempoteoría de la complejidad computacional

Cómo encontrar el subconjunto contiguo de suma máxima utilizando un método de divide y vencerás

¿Qué significa front = rear = null y front = rear = -1 en la cola de las estructuras de datos en C ++?

¿Cuál es la mejor manera de depurar un algoritmo recursivo?

¿Qué algoritmo deberíamos usar para maximizar el CTR y predecir el CTR al mostrar un anuncio?

¿Cuál es la forma correcta de escribir un algoritmo? ¿Podemos usar la sintaxis del lenguaje en el que estamos escribiendo?

¿Cuáles son las diferentes formas en que puede reparar arañazos en su lente Canon EF 85mm?

Una ecuación matemática no tiene una complejidad temporal en sí misma. Un algoritmo que calcula el valor de una ecuación lo hará, pero está sujeto al algoritmo preciso. Dicho esto, las operaciones matemáticas primitivas generalmente se consideran O (1) a menos que esté operando en variables que no tienen un tamaño estático. Entonces, si está calculando un valor en un lenguaje como haskell con números de tamaño dinámico o si está implementando hardware, entonces tiene sentido molestarse con la complejidad en este contexto.

Dicho todo esto, si no está utilizando números de tamaño dinámico, entonces el tamaño de sus datos no está creciendo con cada operación, así que agregue la notación O de las diversas operaciones secuenciales y reduzca:

ejemplo: x * y + z * w

r1 = x * y -> O (n ^ 2) [usando la multiplicación larga del libro de texto]
r2 = z * w -> O (n ^ 2)
r1 + r2 -> O (n)
O (n ^ 2) + O (n ^ 2) + O (n) = O (n ^ 2)

Si está utilizando números numéricos de tamaño dinámico, o cualquier algoritmo que aumente el tamaño a medida que se necesita más precisión, también debe considerar cómo cada función aumenta el tamaño de entrada para la siguiente función al considerar la complejidad del espacio.