Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: C. Sortowanie bąbelkowe.
Sortowanie bąbelkowe (bubble sort) ma złożoność obliczeniową O(n2) w najgorszym przypadku. Jest to jedna z prostszych metod sortowania, która polega na porównywaniu sąsiednich elementów i zamianie ich kolejności, jeśli nie są w odpowiedniej kolejności.
Dlaczego inne odpowiedzi są nieprawidłowe:
A. Wyszukiwanie binarne. – Wyszukiwanie binarne ma złożoność obliczeniową O(log n) i jest efektywniejsze niż sortowanie bąbelkowe.
B. Wypisanie elementów. – Wypisanie elementów tablicy ma złożoność obliczeniową O(n) i jest prostym algorytmem, który nie wymaga sortowania.
D. Sortowanie szybkie. – Sortowanie szybkie (quick sort) ma złożoność obliczeniową O(n log n) i jest efektywniejsze niż sortowanie bąbelkowe.
Chcesz poćwiczyć całą kwalifikację INF.04?
Egzamin próbny na czas, nauka działami, losowe pytanie albo przegląd całej bazy — wszystko w przeglądarce i bez zakładania konta.
Pojęcia z tego pytania
- Sortowanie bąbelkowe (Bubble Sort)Prosty algorytm sortowania o złożoności O(n^2), wielokrotnie porównujący sąsiednie elementy i zamieniający je miejscami, jeśli są w złej kolejności.
- Wyszukiwanie binarne (Binary Search)Algorytm wyszukiwania w posortowanej tablicy o złożoności O(log n), porównujący szukaną wartość ze środkowym elementem i odrzucający połowę zbioru.
- Sortowanie szybkie (Quicksort)Wydajny algorytm sortowania oparty na paradygmacie 'dziel i zwyciężaj', wykorzystujący element osiowy (pivot) do partycjonowania tablicy.
Podobne pytania z działu „Algorytmy sortowania i wyszukiwania”
Ten sam obszar materiału z kwalifikacji INF.04. W całej bazie znajdziesz 23 pytań z tego działu.
- #93
Aby zaprojektować zestaw danych do zainicjowania algorytmu sortowania bąbelkowego tablicy, należy zastosować przynajmniej typy:
- #103
Metoda poszukiwań w tablicach posortowanych, która polega na podzieleniu tablicy na kilka bloków i wyszukaniu liniowym tylko w tym bloku, w którym docelowy element może się znajdować, w języku angielskim nosi nazwę
- #143
Strategia budowania algorytmu poprzez podział na dwa lub więcej mniejszych podproblemów tak długo, aż fragmentu staną się proste do bezpośredniego rozwiązania jest metodą:
- #144
Z tabeli przedstawiającej złożoność obliczeniową algorytmów sortowania na dowolnym, dużym, zbiorze wejściowym (ponad 100 elementów) wynika, że najszybszą metodą jest algorytm sortowania:
- #156
Wskaż niestabilny algorytm sortowania