«Информатиканың теориялық негіздері»
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Бинарлық қоюлар арқылы сұрыптау.
- Есептеу күрделілігі
- Тез сұрыптау Тез сұрыптау әдісі – күнделікті тәжірибеден алынған. Мысалы
- Сұрыптау принципі
| Есептеу күрделілігі: жалпы салыстырулар саны -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.
Бинарлық қоюлар арқылы сұрыптау. Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі. Есептеу күрделілігі: Енгізу орыны табылады егер, al<=item<=ar болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log2i) рет бөлінеді деген сөз. Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі. Тез сұрыптау Тез сұрыптау әдісі – күнделікті тәжірибеден алынған. Мысалы: Аттары бойынша алфавиттік карточкалар жиынын қандай да бір әріпке қатысты, мысалы К, екі кіші жиынға бөлуге болады. Барлық К-дан кіші немесе тең тең болатын бір жиынға, К-дан үлкен болатын бір жиынға бөлеміз. Одан кейін әрбір жиын тағы да екіге бөлінеді т.с.с. Тез сұрыптау алгоритмінде орталық элементті анықтап, сол арқылы бөлу әдісі қолданылады. Яғни, алғашқы массив екіге бөлінеді. Орталық элементтен үлкен және орталық элементтен кіші. Тура осы әрекет алынған массивтің 2 бөлігіне де жүргізіледі. Осылайша бөліне береді. Әрбір бөлікте бір ғана қалғанша жалғастырамыз. Сұрыптау принципі: Массивтің орталық элементі таңдап алынады. Массивтің барлық элементтері солдан оңға және оңнан солға қарай қарап өтіледі. І. Солдан оңға қарай қозғалғанда A[scan up] деген элементті іздейміз және бұл элемент орталық элементтен үлкен болуы керек, оның позициясын есімізге сақтап аламыз. Оңнан солға қарай қозғалғанда A[scan down] деген элементті іздейміз. Ол элемент орталық элементтен кіші немесе тең болады. Позициясын есте сақтаймыз. Табылған элементтердің орындарын ауыстырамыз және scan up және scan down индекстері қиылысқанша іздеуді жалғастырамыз. 1-этапты орындап болғаннан кейін алғашқы масситің элементтері орталық элементке бөлінеді. 2-этапта 1-этаптың әрекеттері массивтің оң жақ және сол жақ бөліктері үшін жеке-жеке орындалады. 3-этапта осы әрекеттердің барлығы 4 бөлігі үшін жеке-жеке орындалады. 4-этапта 4 бөлігі жеке-жеке орындалады. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|