esto puede ser una pregunta tonta, pero quiero calcular la complejidad de uno de mis algoritmos, y no estoy seguro de qué complejidad considerar para la función memmove().¿Debería considerar memmove() O (n) u O (1)?
¿Puedes ayudar/explicar?
void * memmove (void * destination, const void * source, size_t num);
Así es la complejidad O (num) u O (1). Supongo que es O (num), pero no estoy seguro ya que me falta la comprensión de lo que sucede bajo el capó.
Dado que el tiempo de ejecución de memmove aumenta en proporcionalidad directa con el número de bytes que se requiere para moverse, es O (n).
O (n) es la complejidad asintótica correcta, pero no creo que usaría el término "proporcionalidad directa" en este contexto, incluso para algo tan simple como 'memmove'. Considere n = 4 frente a n = 1 bytes en una arquitectura de 32 bits: el caso n = 1 podría ser la operación más cara. –
Es 'O (n)' donde 'n' es el recuento pasado a' memmove() '- pero eso puede no ser proporcional a la' n' que está usando para caracterizar su algoritmo. – caf
¿Qué está aplicando la operación memmove() para - elementos seleccionados en el algoritmo o todos ellos? ¿Está aplicando memmove() a elementos más de una vez?
Esas son las cosas que importarán a la complejidad del algoritmo.
Esa respuesta puede ser diferente que la complejidad de memmove() sí mismo con respecto a las matrices de char elementos que memmove() trata de (para el que memmove() es un (n) la operación O).
La respuesta correcta es, probablemente, que depende de la implementación. Puede imaginarse un sistema inusual en el que la memoria es realmente un gráfico complejo o una lista vinculada. En todos los sistemas reales que conozco, es proporcional a num. –