En el Análisis de Complejidad, ¿por qué ++ se considera 2 operaciones?

StackOverflow https://stackoverflow.com/questions/443423

Pregunta

En mi clase de Informática II, el profesor considera que ++, -, * =, etc. son 2 operaciones. Sin embargo, a nivel de Asamblea, esto no es realmente dos operaciones. ¿Alguien puede explicar o es solo por simplicidad?

¿Fue útil?

Solución

Realmente lo consideraría como 3 operaciones: lectura, incremento (o lo que sea), escritura. Eso supone que está leyendo desde algún tipo de memoria compartida en algún tipo de almacenamiento local (por ejemplo, registro o pila), operando en el almacenamiento local y luego escribiendo de nuevo.

La cantidad de operaciones a nivel de ensamblaje dependerá de lo que esté incrementando, la plataforma, el hardware, etc.

Otros consejos

Porque ++ (ej: b ++) es una simplificación de 

b = b + 1

Hay dos operaciones allí, la suma (b + 1) y luego la asignación del valor de la suma a la variable original.

¿Por qué molestarse al hacer análisis de complejidad? Es solo O (1) :-)

EDITAR: Avísame por qué cuando lo rechaces. Como la pregunta está etiquetada como complejidad , supongo que la noción O grande es la más importante, en lugar de las constantes reales. Además, como ya se mencionó en otras respuestas, cuántas operaciones depende de muchos factores: la forma en que cuenta las operaciones, la plataforma, el compilador, etc.

Voy a hacer algunas conjeturas.

  • ¿Se refiere su profesor a los idiomas interpretados?
  • ++ i es diferente de i ++ ¿tal vez se está refiriendo a eso?

  • ¿Tal vez su elección de ensamblaje necesita la variable de almacenamiento intermedio? 

    add reg_temp, reg_i, 1
mov reg_i, reg_temp

¿No es una adición más un setter?

¿Similar a i + = 1?

El profesor probablemente solo se refiera a tener que tomar el valor, agregarle 1 y luego asignarlo nuevamente a la variable.

En el nivel de ensamblaje, todo se hace en registros, por lo que tener una variable en A 

ADD AX,1

Sin embargo, en los lenguajes compilados todo debe almacenarse para que i ++ se convierta (en pseudo ensamblaje) 

MOV AX,i
ADD AX, 1
MOV i, AX

Que son tres operaciones ... A menos que haya olvidado por completo mi arquitectura básica ...

Me recordó a un poco " Jurado no está fuera " problema que escuché hace mucho tiempo.

  

" Preincrement es más rápido que postincrement "

Acabo de hacer una búsqueda rápida en Google.

  1. Mucha gente todavía lo considera cierto.
  2. Otros sostienen que los compiladores están tan optimizados que el código de código de alto nivel comparativo no puede ser comparado.
  3. Sin embargo, otras personas afirman que no hay diferencia .

Debería ser más de 2 en mi opinión, ya que tiene dos significados según el contexto y siempre tengo que recordarlos cuando los veo.

a = b ++ es lo mismo que a = b; b = b + 1

y

a = ++ b es lo mismo que b = b + 1; a = b

Esto es suficiente confusión para enviar a la mayoría de los estudiantes de primer año al precipicio.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top