Әдістемелік құрал
сұрыптауы деп аталады. Есептеу күрделілігі
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
- Бұл бет үшін навигация:
- Есептеу күрделілігі
| сұрыптауы деп аталады.
Есептеу күрделілігі. Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n 2 ) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді. Қою арқылы сұрыптау Қою арқылы сұрыптау – келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға: 50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек. 50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту. 40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту. 75-ті 3 позициясына қыстыру. 35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту. Есептеу күрделілігі: жалпы салыстырулар саны 2 ) 1 ( − n n -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n 2 )-ге тең. Бинарлық қоюлар арқылы сұрыптау. Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі. Есептеу күрделілігі: Енгізу орыны табылады егер, a l <=item<=a r болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log 2 i) рет бөлінеді деген сөз. 67 = i n i 2 log 1 Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі. жүктеу/скачать 1,24 Mb. Достарыңызбен бөлісу:
|