Jaka jest złożoność czasowa inicjowania macierzy?

Question

Rozważmy następujący dwóch przypadkach inicjalizacji tablicy w C lub C++:

Przypadek 1:

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

Przypadek 2:

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

Czy oboje podejmują samym czasie? jaka jest złożoność sprawy 1? i który z nich jest lepszy?

Answer 1

W przypadku tablica jest od czasu trwania statycznego (zmienna globalna), powiedziałbym, że pierwszy jest znacznie preferowalny, ponieważ nie wymaga żadnego kodu - jest inicjowany przez środowisko wykonawcze.

Jeśli zmienna jest automatycznym czasem trwania (zmienna lokalna), która z nich jest lepsza, jeśli jedna jest lepsza od drugiej, zależy od kompilatora. Najprawdopodobniej obie będą bardzo podobne.

Kombinacja dla zmiennej czasu trwania automatycznego składowania wynosi O (n) dla wszystkich przypadków. Pierwszy przypadek to O (1) dla zmiennej czasu przechowywania statycznego.

Oczywiście, jeśli chcesz wypełnić tablicę wartością 5, druga opcja jest znacznie lepsza, ponieważ nie wymaga zapisu 10000 5 w pliku źródłowym.

Może się również okazać, że używanie memset(array, 0, sizeof(array)); jest lepsze niż oba - ponownie, w zależności od kompilatora. To nadal jest O (n), ale faktyczny czas wypełnienia tablicy może być krótszy, ponieważ memset może być lepiej zoptymalizowany niż to, co kompilator generuje dla twojego przypadku pętli [i co robi dla zainicjowanych zmiennych]. memset nie będzie działał również przy wypełnianiu tablicy z 5.

Można również użyć std::fill(array, &array[10000], 5);, aby ustawić wartość 5 we wszystkich tablicach, a kompilator wykona przyzwoite zadanie optymalizacji.

Na koniec powinienem zaznaczyć, że takie rzeczy są NAPRAWDĘ ważne, jeśli robią to w kodzie, który jest często wykonywany. Minęło dużo czasu od czasu, gdy wypełnienie 40 KB danych zajęło wystarczająco dużo czasu, aby naprawdę się martwić. Jak ponad 20 lat.

Answer 2

Teoretycznie oba mają ten sam czas złożoności: O(N), gdzie N jest wielkością twojej tablicy.

Jednak pierwsza metoda powinna być lepsza, ponieważ od kompilatora zależy, jak wybrać tak szybko, jak to możliwe (na przykład można to zrobić poprzez memset). W celu optymalizacji kompilator jest często lepszy niż programista.

BTW, jeśli tablica ma statyczny czas przechowywania (jeśli zadeklarować ją jako zmienną globalną, na przykład), to będzie automatycznie inicjowany na 0.