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 log n)
D. O(n³)
Złożoność obliczeniowa przedstawionego algorytmu wynosi O(n³), co wynika z trzech zagnieżdżonych pętli, z których każda iteruje po n elementach. W praktyce oznacza to, że liczba operacji, które algorytm wykonuje, rośnie proporcjonalnie do sześcianu liczby n. Przykładowo, jeśli mamy dwa wymiary, złożoność będzie O(n²), ale w tym przypadku mamy trzy wymiary (i, j, k), co podwyższa złożoność do O(n³). Takie sytuacje zdarzają się często w problemach związanych z przetwarzaniem danych w trzech wymiarach, takich jak grafika komputerowa czy analiza danych 3D. W branży, dobrze jest pamiętać, że złożoność O(n³) może być nieefektywna dla dużych n, dlatego warto analizować algorytmy pod kątem ich wydajności i stosować różne techniki optymalizacji, jak na przykład podział danych czy struktury danych zmniejszające złożoność. Warto również zrozumieć, że dla dużych wartości n, czas wykonania algorytmu może być zauważalnie dłuższy, co wpływa na ogólną efektywność systemu.
