Pewien algorytm jest szybszy od algorytmu wyszukiwania liniowego. Oznacza to, że jego złożoność obliczeniowa to
Pewien algorytm jest szybszy od algorytmu wyszukiwania liniowego. Oznacza to, że jego złożoność obliczeniowa to
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź to A. Wyszukiwanie liniowe ma złożoność O(n). Algorytm szybszy musi mieć mniejszą złożoność, np. O(\log n) (jak wyszukiwanie binarne).
Wyjaśnienie pozostałych opcji:
- O(n) – To ta sama złożoność co wyszukiwanie liniowe.
- O(n+m) – To złożoność liniowa (zależna od dwóch zmiennych).
- O(n^2) – To złożoność kwadratowa, znacznie wolniejsza od liniowej.
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
- Pojęcie i Cechy AlgorytmuUporządkowany, skończony i jednoznaczny ciąg instrukcji i kroków postępowania prowadzący do rozwiązania określonego problemu obliczeniowego dla poprawnych danych wejściowych.
- 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.
- 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: