Pytanie 1
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; } } }
A. O(n)
B. O(n²)
C. O(n³)
D. O(n log n)
Złożoność obliczeniowa algorytmu to kluczowy aspekt, który decyduje o jego efektywności, a odpowiedzi takie jak O(n²), O(n log n) czy O(n) wynikają z powszechnych nieporozumień. Odpowiedź O(n²) może pojawić się, gdy ktoś myśli jedynie o największej pętli, nie uwzględniając pełnej hierarchii zagnieżdżonych pętli. Jednakże, w tym przypadku mamy do czynienia z trzema niezależnymi pętlami, a każda z nich przechodzi przez n iteracji, co prowadzi do O(n³). Z kolei O(n log n) jest typowe dla algorytmów sortujących, takich jak sortowanie szybkie czy sortowanie przez scalanie, lecz nie ma zastosowania w kontekście zagnieżdżonych pętli, które wykonują prostą operację przypisania. Odpowiedź O(n) wskazuje na liniową złożoność, co jest błędne w przypadku dwóch lub więcej wymiarów. Takie myślenie często prowadzi do błędnych ocen złożoności algorytmu, zwłaszcza, gdy nie uwzględnia się wszystkich aspektów zagnieżdżenia pętli. Ważne jest, aby przy analizowaniu złożoności obliczeniowej, zawsze uwzględniać wszystkie zagnieżdżone elementy, by uzyskać dokładny obraz wydajności algorytmu.
