Evaluación escrita en operación aritmética

Question

Perdón por mi mal inglés.

A menudo veo la siguiente frase

en tiempo polinómico $O(n^2)$ operación aritmética en $\mathbb{Z}$

o

en tiempo polinómico $O(n^2)$ operación aritmética en $\mathbb{F}_q$

¿Es mi interpretación "operación aritmética en $\mathbb{F}_q$ "¿Es correcto?

es decir, por ejemplo, un cálculo $(5+3)\times (3-1)$ es $(5+3)\times (3-1)=8\times (3-1)=8\times 2=16$ por lo que tenemos 3 operaciones aritméticas en $\mathbb{Z}$ .

Si la interpretación anterior es cierta, ¿podemos contar "suma" y "multiplicación"? Creo que hay una gran diferencia en el punto del tiempo entre "suma" y "multiplicación".

Por favor, ayúdame.

Answer 1

Depende del contexto. El redactor debe especificar qué operaciones son "costoso" & que son "fácil" entonces el algoritmo dado puede ser analizado para estimar el número de operaciones costosas & entonces reclamar $O(n^2)$ Etc.

Hay casos en los que la "comparación" es la operación principal (por ejemplo, la ordenación) y los algoritmos cuentan que la operación de declarar que, por ejemplo Bubble Sort es $O(n^2)$ u otro algoritmo de ordenación es $O(n\log{n})$ Etc. Estos algoritmos pueden incluir multiplicaciones y sumas, que son más costosas pero no contribuyen mucho al tiempo total de ejecución.

Hay algoritmos en los que la "comparación" es irrelevante, ya que lo importante es la multiplicación y la suma. Por ejemplo, la suma de matrices o la multiplicación de matrices.
En ese caso , el escritor especificará que la Multiplicación y la Suma son igualmente costosas para luego contarlas ambas.
Alternativamente, el escritor especificará que la Multiplicación es muy costosa (podemos ignorar la Suma) y por lo tanto contará las Multiplicaciones.

Por lo tanto, dependiendo del contexto, su ejemplo tiene: 3 operaciones (1 multiplicación + 2 sumas) o 1 operación (1 multiplicación) o 2 operaciones (1 multiplicación + 1 suma, ignorando la "operación de disminución").

En algunos casos, se trata de números en coma flotante y todos los cálculos son igualmente costosos, incluyendo "comparación", "multiplicación", "suma", "operación de incremento", "operación de decremento", "funciones de potencia", "funciones trigonométricas", "funciones logarítmicas", etc. A continuación, contamos todas estas operaciones en el total.