ID: 2664
Algorytmy
Średnie
Źródło: Arkusze CKE
Z analizy złożoności obliczeniowej algorytmów sortowania dla dużych zbiorów danych (powyżej 100 elementów) wynika, że najefektywniejszą metodą jest algorytm sortowania:
sortowanie bąbelkoweO(n²)sortowanie przez wstawianieO(n²)sortowanie przez scalanieO(n log n)sortowanie przez zliczanieO(n)sortowanie kubełkoweO(n²)
Warianty odpowiedzi
-
A
kubełkowego
-
B
przez zliczanie
-
C
bąbelkowego
-
D
przez scalanie
Wyjaśnienie
W tym pytaniu należy zwrócić uwagę na zestawienie złożoności podanych w treści zadania oraz specyfikę testów egzaminacyjnych.
Spośród algorytmów opartych na porównaniach, najefektywniejsze jest sortowanie przez scalanie ze złożonością O(n log n), co idealnie sprawdza się przy dużych zbiorach danych.
W oficjalnym kluczu do tego pytania wskazano sortowanie przez zliczanie, jednak wymaga ono spełnienia dodatkowych założeń dotyczących zakresu liczb. Na egzaminie warto zapamiętać tabelę złożoności i kojarzyć wysoki poziom wydajności O(n log n) lub O(n) zależnie od typu algorytmu.