ID: 2753
Algorytmy
Średnie
Źródło: Arkusze CKE
Jaka jest złożoność obliczeniowa poniższego algorytmu?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
array[i][j][k] = i + j + k;
}
}
}
Warianty odpowiedzi
-
A
O(n log n)
-
B
O(n²)
-
C
O(n³)
-
D
O(n)
Wyjaśnienie
Patrząc na ten kod, widzimy trzy pętle for zagnieżdżone jedna w drugiej.
Każda z tych pętli wykonuje się n razy. Najbardziej wewnętrzna operacja przypisania wartości wykona się więc n razy n razy n kroków.
W zapisie matematycznym daje to n do potęgi trzeciej wykonanych operacji.
Stąd złożoność obliczeniowa tego algorytmu wynosi O(n^3).