ID: 1985
Algorytmika
Łatwe
Źródło: Arkusze CKE
Algorytm wyszukiwania elementu w nieposortowanej tablicy jednowymiarowej ma złożoność obliczeniową
Warianty odpowiedzi
-
A
A. stałą, O(1)
-
B
B. silnia, O(n!)
-
C
C. liniową, O(n)
-
D
D. kwadratową, O(n2)
Wyjaśnienie
Pomyśl o tym jak o szukaniu konkretnej książki na niesporządkowanym stosie. Nie masz żadnego porządku, więc nie możesz zastosować żadnego sprytnego skrótu.
Musisz brać po kolei każdą książkę i sprawdzać, czy to ta. W najlepszym przypadku trafisz od razu na pierwszą. Ale w programowaniu zawsze przygotowujemy się na pesymistyczny scenariusz.
W najgorszym wypadku poszukiwany element będzie na samym końcu albo nie będzie go wcale. To oznacza, że musisz wykonać dokładnie tyle sprawdzeń, ile jest elementów w tablicy. Jeśli tablica ma n elementów, robisz n kroków. Stąd bierze się złożoność liniowa, którą w notacji zapisujemy jako O(n).