W celu optymalizacji programu działającego na uporządkowanym zbiorze można zastosować metodę wyszukiwania:
W celu optymalizacji programu działającego na uporządkowanym zbiorze można zastosować metodę wyszukiwania:
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź to C (przy założeniu, że pytanie dotyczy szybkiego wyszukiwania w zbiorze uporządkowanym). Wyszukiwanie binarne (przeszukiwanie połówkowe) ma złożoność O(log n) i jest znacznie szybsze od liniowego, ale wymaga posortowanych danych.
Wyjaśnienie pozostałych opcji:
- A – Wyszukiwanie liniowe sprawdza każdy element po kolei (O(n)).
- B – "Bąbelkowe" odnosi się do sortowania, a nie wyszukiwania.
- D – Wyszukiwanie z wartownikiem to wariacja wyszukiwania liniowego (nadal O(n)).
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
- Wyszukiwanie liniowe i z wartownikiem (Linear Search)Podstawowy algorytm przeszukiwania tablicy sprawdzający elementy kolejno od początku do końca o złożoności O(n), nie wymagający posortowania danych.
- 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.
- Złożoność obliczeniowa (Big O Notation)Formalna miara efektywności algorytmu określająca zapotrzebowanie na czas procesora lub pamięć w funkcji rozmiaru danych wejściowych (n).
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ę
- #129
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
- #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: