Алгоритмдер жєне деректер структурасы



бет18/42
Дата03.01.2022
өлшемі0.9 Mb.
#451095
1   ...   14   15   16   17   18   19   20   21   ...   42
«алгоритмдер ж не деректер рылымы»1

Анықтама. Итерация дегеніміз алгоритмді енгізілетін деректерге қолдану операциясы. Әрбір келесі итерацияның бастапқы берілгендері болып оның алдындағы итерацияда анықталған мәндер алынады.

Егер массив реттелмеген болса, онда біртіндеп іздеу әдісін қолдануға болады:

A[1..n] массиві берілсін. P-ға тең элементті іздеу керек болсын.

1. i=1; болғанда бастаймыз

2. егер ai=p шарты орындалса, онда іздеу сәтті аяқталады

3. әйтпесе I:=i+1 деп келесі элементке көшеміз

4. егер i<=n болса, онда 2-ші пунктке көшеміз, әйтпесеәздеу сәтсіз аяқталады.

Бұл алгоритмнің күрделілігі n-1-ге тең, себебі элементтерді р-мен салыстыру саны сонша.


5. реттелмеген массивте бинарлы іздеу алгоритмі

Егер массив реттелген болса, онда бинарлы-екілік іздеуді қолдануға болады. Оны логарифмдік іздеу немесе дихотомия әдісі дейді.

Мұнда екі көрсеткіш пайдаланады: l=1 массивтің алғашқы элементін көрсетеді, u=n массивтің соңғы элементін көретеді:

1. l=1; u=n; болады

2. егер ul<=k<=au шартының орындалатынын білеміз. I=(l+u) div 2 деп аламыз , сонда I массивтің ортасын көрсетеді.

3. Егер ki болса, онда 4-ші пунктке көшеді, егер k>ai болса, онда 5-ші пунктке көшеді, егер k=ai болса, онда іздеу сәтті аяқталады.

4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз

5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз.

Бұл алгоритмде күрделілік дәрежесі -ге тең болады.



Достарыңызбен бөлісу:
1   ...   14   15   16   17   18   19   20   21   ...   42




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет