Was ist die zeitliche Komplexität der Array-Initialisierung?

Question

folgenden zwei Fälle von Array-Initialisierung in C oder C++ vor:

Fall 1:

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

Fall 2:

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

Sie sie beide gleiche Zeit in Anspruch nehmen? Wie komplex ist Fall 1? und, welcher ist besser?

Answer 1

Im Fall sein die Anordnung von statischer Dauer sein (globale Variable), würde ich sagen, die erste ist viel vorzuziehen, da sie keinen Code benötigt - sie wird von der Laufzeitumgebung initialisiert.

Wenn die Variable eine automatische Dauer hat (lokale Variable), welche davon besser ist, wenn die eine besser ist als die andere, hängt vom Compiler ab. Höchstwahrscheinlich werden sich beide sehr ähnlich sein.

Die Eigenschaft für die automatische Speicherdauer ist in allen Fällen O (n). Der erste Fall ist O (1) für eine statische Speicherdauervariable.

Natürlich, wenn Sie Array mit dem Wert 5, die zweite Option ist viel besser füllen wollten, weil es nicht 10000 5 in der Quelldatei zu schreiben erfordert.

Sie können auch finden, dass die Verwendung von memset(array, 0, sizeof(array)); ist besser als beide - wieder, je nach Compiler. Dies ist immer noch O (n), aber die tatsächliche Zeit, die zum Füllen des Arrays benötigt wird, kann kürzer sein, weil memset möglicherweise besser optimiert ist als das, was der Compiler für Ihren Loop-Fall generiert [und was er für initialisierte Variablen tut]. memset funktioniert nicht zum Füllen des Arrays mit 5 entweder.

Sie könnten auch std::fill(array, &array[10000], 5); verwenden, um den Wert 5 im gesamten Array zu setzen, und der Compiler sollte einen guten Job haben, diesen zu optimieren.

Schließlich sollte ich darauf hinweisen, dass diese Art von Dingen nur dann wirklich wichtig ist, wenn sie in Code tun, der viel ausgeführt wird. Es ist lange her, dass 40KB Daten lange genug benötigt wurden, um sich wirklich um sich selbst zu kümmern. Wie 20+ Jahre.

Answer 2

In der Theorie haben beide die gleiche Zeitkomplexität: O(N), wobei N die Größe Ihres Arrays ist.

Die erste Methode sollte jedoch besser sein, da es der Compiler ist, zu wählen, wie man so schnell wie möglich initialisiert (zum Beispiel könnte es durch memset getan werden). Für Optimierungen ist der Compiler oft besser als der Programmierer.

BTW, wenn Ihr Array statische Speicherdauer hat (wenn Sie es als globalen Variable, zum Beispiel erklären), wird es automatisch initialisiert auf 0