Asignar / establecer un valor es una de las operaciones más fundamentales para un algoritmo. Las operaciones se basan en instrucciones. Entonces sí, necesitas contarlos.
Quería pasar el resto de mi respuesta explicando algunos matices de la respuesta de Rohit Chauhan a ¿Podemos contar una tarea como instrucción mientras calculamos un algoritmo? no consideró correctamente el cálculo de la complejidad de un algoritmo. Estoy de acuerdo con la primera parte de la respuesta de Rohit, pero no creo que sus afirmaciones posteriores sean completamente precisas. Puede hacer la primera parte de eso, pero creo que esto pierde el panorama general de por qué puede hacer esto.
“Pero en el caso de calcular la complejidad de un algoritmo, tales asignaciones se descuidan ya que son una operación de tiempo constante. Los bucles y las operaciones condicionales múltiples son las que le cuestan más en términos de complejidad “.
- ¿Debería centrarme en el aprendizaje de algoritmos y estructuras de datos en profundidad, o aprender una habilidad como desarrollo web o desarrollo móvil usando Nanodegree?
- ¿Qué es mejor para eliminar números específicos de una matriz, Java o C ++?
- ¿Cómo unir y dividir funciona en un Treap al agregar o eliminar un elemento?
- ¿Es normal tener un título en CS y no ser capaz de implementar algoritmos simples?
- Dada la secuencia creciente, en cada paso puede elegir 2 elementos consecutivos, reemplazarlos con su suma y no puede elegir el último elemento, ¿cuál es el número máximo de movimientos que puede hacer para que la secuencia siga aumentando?
No estoy de acuerdo con esta interpretación. No es que descuidemos estas tareas, depende de dónde ocurran (como en cuántas veces ocurren). Déjame darte un ejemplo, aquí está BubbleSort (de Bubble sort – Wikipedia):
Las líneas alrededor del azul (pido disculpas por el descuido, solo estaba usando la herramienta de recorte), cualquiera de estos debería ser suficiente en el peor de los casos para contar para obtener la función de crecimiento con la que desarrolla el límite asintótico. Observe que tanto swap (A [i-1], A [i]) como swapped = true son técnicamente un número constante de declaraciones de asignación. ¿Pero adivina que? El número de estos se basa completamente en el tamaño de entrada debido al bucle for. Puede ir a la derecha para el bucle for en la parte superior (que es lo que creo que Rohit dice), pero eso sería ignorar la razón por la que contaría el bucle for en lugar de lo que está dentro del bucle for, ya que todos Las líneas de pseudocódigo (sin incluir los comentarios, obviamente) son líneas válidas para contar. No descuidamos estas líneas. Es solo porque se supone que las asignaciones toman un tiempo constante por lo que usted va directamente al ciclo for, pero como dije, bajo esta suposición, cualquiera de estas líneas es correcta para contar como un barómetro para derivar la función de crecimiento en el análisis. De hecho, podría contar todas las líneas que he indicado y todas las demás que se ejecutan en el peor de los casos y producen exactamente el mismo límite asintótico. Dicho esto, estas líneas se pueden descuidar (no es que se descuiden), observe la diferencia.
“Si se escribe un algoritmo, se deben mencionar todos los pasos, inicialización, asignación, entradas (a veces esto también se toma en cálculos de complejidad de tiempo), condiciones, etc.”
No, cuando analizamos un algoritmo, siempre debemos considerar el tamaño de entrada (entradas) al analizar el algoritmo. De lo contrario, podría estar engañando a las personas sobre la eficacia de su algoritmo.
