¿Cuál es la complejidad temporal de la inicialización de la matriz?

¿Cuál es la complejidad temporal de la inicialización de la matriz?


Considere seguir dos casos de inicialización de Array en C o C++:


Caso 1:


int array[10000] = {0}; // All values = 0

Caso 2:


int array[10000];
for (int i = 0; i < 10000; i++) {
array[i] = 0;
}

¿Toman los dos el mismo tiempo? ¿Cuál es la complejidad del Caso 1? y, ¿Cuál es mejor?


Respuestas:


En el caso de que la matriz tenga una duración estática (variable global), diría que la primera es mucho más preferible, ya que no requiere ningún código:el entorno de tiempo de ejecución la inicializa.


Si la variable es de duración automática (variable local), cuál es mejor, si alguna es mejor que la otra, depende del compilador. Lo más probable es que ambos sean muy similares.


La complejidad para la variable duración del almacenamiento automático es O(n) para todos los casos. El primer caso es O(1) para una variable de duración de almacenamiento estática.


Por supuesto, si desea llenar la matriz con el valor 5, la segunda opción es mucho mejor porque no requiere escribir 10000 5 en el archivo fuente.


También puede encontrar que usar memset(array, 0, sizeof(array)); es mejor que ambos, nuevamente, dependiendo del compilador. Esto sigue siendo O(n), pero el tiempo real que lleva llenar la matriz puede ser más corto, porque memset puede estar mejor optimizado que lo que genera el compilador para su caso de bucle [y lo que hace para las variables inicializadas]. memset no funcionará para llenar la matriz con 5 o.


También puedes usar std::fill(array, &array[10000], 5); para establecer el valor 5 en toda la matriz, y el compilador debería hacer un trabajo decente para optimizar eso.


Finalmente, debo señalar que este tipo de cosas solo importan REALMENTE si se realizan en un código que se ejecuta mucho. Ha pasado mucho tiempo desde que llenar 40 KB de datos tomó el tiempo suficiente como para preocuparse por sí solo. Como más de 20 años.