Programista chce dobrać najszybciej działający algorytm przetwarzania danych w swojej aplikacji. Na podstawie przedstawionej w tabeli złożoności obliczeniowej, należy wybrać algorytm numer

Poprawna odpowiedź: C

Uzasadnienie i szersze wyjaśnienie:

Złożoność obliczeniowa (w notacji Wielkiego O) opisuje, jak czas wykonania algorytmu rośnie wraz ze wzrostem ilości danych (n). „Najszybszy” algorytm to ten, którego funkcja złożoności rośnie najwolniej.

Porównajmy podane złożoności od najwolniejszej do najszybszej:

• O(n!) (złożoność silniana) - Algorytm 2. Jest to najwolniejsza możliwa złożoność, rosnąca astronomicznie szybko. Praktycznie nieużyteczna dla n większego niż kilkanaście.
• O(n³) (złożoność sześcienna) - Algorytm 3. Rośnie bardzo szybko, znacznie wolniej niż silnia, ale wciąż jest nieefektywna dla dużych zbiorów danych.
• O(n²) (złożoność kwadratowa) - Algorytm 1 i 5. Typowa dla prostych algorytmów sortowania, znacznie lepsza niż O(n³), ale wciąż wolna dla dużych n.
• O(n) (złożoność liniowa) - Algorytm 4. Czas wykonania rośnie proporcjonalnie do liczby elementów. Jest to bardzo wydajna i pożądana złożoność.

Z tego porównania jasno wynika, że Algorytm 4 ze złożonością O(n) jest zdecydowanie najszybszy.

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A i B: Algorytmy 2 i 3 mają złożoność silnianą i sześcienną, co czyni je najwolniejszymi z całego zestawienia.
• D: Algorytmy 1 i 5 mają złożoność kwadratową, która jest znacznie wolniejsza niż liniowa złożoność algorytmu 4.