ID: 2619
Algorytmy
Łatwe
Źródło: Arkusze CKE
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n^2)?
Warianty odpowiedzi
-
A
Wyszukiwanie binarne.
-
B
Sortowanie szybkie.
-
C
Wypisanie elementów.
-
D
Sortowanie bąbelkowe.
Wyjaśnienie
Złożoność O(n^2) oznacza w praktyce, że gdy rozmiar danych wejściowych rośnie dwukrotnie, czas wykonania programu wydłuża się aż czterokrotnie. Dzieje się tak, ponieważ algorytm wykonuje operacje w dwóch zagnieżdżonych pętlach.
Sortowanie bąbelkowe jest sztandarowym przykładem takiej wydajności. W najgorszym i średnim przypadku porównuje każdy element z każdym innym, co przy większych zbiorach danych czyni go wysoce nieefektywnym.
Dla porównania: wyszukiwanie binarne działa w czasie logarytmicznym O(log n), Quicksort osiąga średnio O(n log n), a zwykłe jednorazowe przejście po tablicy to złożoność liniowa O(n).