Лекция тезистері
жүктеу/скачать 382.54 Kb.
|
- Бұл бет үшін навигация:
- 5. реттелмеген массивте бинарлы іздеу алгоритмі
- Реттеу, сұрыптау алгоритмі
| Анықтама. Итерация дегеніміз алгоритмді енгізілетін деректерге қолдану операциясы. Әрбір келесі итерацияның бастапқы берілгендері болып оның алдындағы итерацияда анықталған мәндер алынады.
Егер массив реттелмеген болса, онда біртіндеп іздеу әдісін қолдануға болады: 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. егер u 3. Егер k 4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз 5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз. Бұл алгоритмде күрделілік дәрежесі -ге тең болады. Реттеу, сұрыптау алгоритмі Деректерге көп қолданылатын амалдардың бірі – сұрыптау. Сұрыптау дегеніміз – массив элементтерін белгілі бір ережені сақтайтындай етіп, реттеп орналастыру. Сұрыптау ішкі және сыртқы деп бөлінеді. Сыртқы сұрыптауға сыртқы жадыдағы деректерді сұрыптау жатады. Ал ішкі сұрыптауға ішкі жадыға деректерді реттеп орналастыру жатады. Ішкі сұрыптау бірнеше әдіспен орындалады: жүктеу/скачать 382.54 Kb. Достарыңызбен бөлісу:
|