Podcast
Play an AI-generated podcast conversation about this lesson
Questions and Answers
Jaką wartość zwróci algorytm z treści po wykonaniu?
Jaką wartość zwróci algorytm z treści po wykonaniu?
- 56
- 3 (correct)
- 5
- 12
Które stwierdzenie opisuje notację asymptotyczną?
Które stwierdzenie opisuje notację asymptotyczną?
- Opisuje wzrost funkcji f(n) jako różnicę dwóch funkcji g(n) dla każdego n mniejszego od n0.
- Opisuje wzrost funkcji f(n) jako iloraz dwóch funkcji g(n) dla każdego n większego od n0.
- Opisuje wzrost funkcji f(n) jako iloczyn stałej c i funkcji g(n) dla każdego n większego od n0. (correct)
- Opisuje wzrost funkcji f(n) jako sumę dwóch funkcji g(n) dla każdego n mniejszego od n0.
Które stwierdzenie dotyczące złożoności pamięciowej jest prawdziwe?
Które stwierdzenie dotyczące złożoności pamięciowej jest prawdziwe?
- Złożoność pamięciowa jest niezależna od sposobu organizacji rekurencji.
- Trudniej określić złożoność pamięciową dla algorytmów operujących na bardzo dużej liczbie danych. (correct)
- Złożoność pamięciowa jest łatwa do określenia dla algorytmów rekurencyjnych.
- Największa zajętość pamięci występuje przy najkrótszym ciągu wywołań rekurencji.
Jakie jest główne działanie algorytmu 'Bubble sort'?
Jakie jest główne działanie algorytmu 'Bubble sort'?
Signup and view all the answers
Jakie stwierdzenie najlepiej opisuje notację 'Big – Oh'?
Jakie stwierdzenie najlepiej opisuje notację 'Big – Oh'?
Signup and view all the answers
Flashcards are hidden until you start studying
Study Notes
Algorytmy i struktury danych - Szukanie liniowe z wartownikiem
-
Problem: Sprawdzenie, czy liczba y występuje w ciągu n liczb x1, x2, …, xn.
-
Specyfikacja:
- Warunek początkowy:
- Dane: liczba y, liczba naturalna n (elementy x1, x2, …, xn).
- Warunek końcowy:
- Wynik: indeks i elementu, dla którego wartość y = xi, lub 0, jeśli y nie występuje.
- Warunek początkowy:
Schemat działania algorytmu
- Ustaw:
ostatni = xn,xn = y,i = 1. - Pętla:
dopóki y ≠ xiwykonaji = i + 1,xn = ostatni. - Warunki zakończenia:
- Jeśli
i < nlubxn = y, zwróći. - W przeciwnym razie zwróć 0.
- Jeśli
Przykład zastosowania
-
Przykład 1:
- y = 6, n = 3, x1 = 56, x2 = 12, x3 = 5.
- Następujące przypisania:
ostatni = xn,xn = y,i = 1. - W iteracjach:
- i = 1: 6 ≠ 56
- i = 2: 6 ≠ 12
- i = 3: 6 = 6 (x3 = 5)
- Uwagi: i = 3, zapewnia, że
x3 ≠ y, więc wynik to 0.
-
Przykład 2:
- y = 5, n = 3, x1 = 56, x2 = 12, x3 = 5.
- Z podobnym przebiegiem, algorytm przeszukuje wartości i ocenia indeksy, dopóki nie znajdzie y lub nie zakończy z n.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
