Әдістемелік құрал
Түзу бірігу сұрыптау анализі
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
- Бұл бет үшін навигация:
- Балансталған көп жолдық бірігу
|
Түзу бірігу сұрыптау анализі Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log 2 n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log 2 n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log 2 n). Табиғи бірігу арқылы сұрыптау. Түзу бірігу арқылы сұрыптауда алғашқы ұзындығы бірге тең болатын реттелген сериялар пайдаланылады да, олар әрбір жүріс сайын екі еселеніп отырады. Ең аяғында сериялар файлдардың барлығын қамтиды да сұрыпталу аяқталады. Мұның бір кемшілігі қысқа сериялар мен жұмыста көп уақыт кетеді. Мұндай сұрыптауды салыстырмалы түрде ұзын сериялардан бастасақ, алгоритмнің тиімділігі неғұрлым артады. Әрбір ретте неғұрлым екі серия бірігетін сұрыпталу әдісі табиғи бірігу деп аталады. Сұрыптау алгоритмі Алғашқыда FC алғашқы файлды және алғашқы ұзындықтағы реттелген серияларды жасау үшін оперативті жадыдағы буфер керек: 1. Алғашқы файлдың мәліметтері буферге блок бойынша оқылады. 2. Әрбір блок сұрыпталудың кез келген алгоритмі арқылы сұрыпталады да (мысалы, тез сұрыпталу), кезек-кезек FB және FA файлдарына көшіріліп отырады. 3. FC файлы біткен кезде қайтадан уақытша FА және FВ файлындағы мәліметтер блоктары қайтадан біріге бастайды. 4. Осылайша, сұрыптау жай бірігуге ұқсас жалғаса береді. Алгоритм анализі: Мұнда әрбір жүрістен сериялардың саны екі есе қысқарады. Сондықтан жіберулердің жалпы саны ең жаман жағдайда n log 2 n тең болады. Ал жалпы жағдайда одан да аз болады. Балансталған көп жолдық бірігу Тізбектелген сұрыпталуға кететін шығын жүрістің санына прорпорционал 72 болады. Шығынды азайтудың бір жолы екі уақытша немесе одан да көп файлдарды пайдалану R сериялы бірігу n уақытша файлдарға бөлінгенде n R ішкі тізімдерден тұратын тізбек құрайды. Екінші жүріс бұл санды 2 n R дейін қысқартады. Ал үшінші жүріс 3 n R дейін қысқартады. Осылайша к жүрістен кейін k n R бөлік қалады. n элементі N жүрісті бірігу мен сұрыптауда жүрістің жалпы саны k=log N n (N-жол, n-элементтер саны) тең болады. Әрбір жүрісте қайта жазудың n операциясы жүретін болғандықтан ең жаман жағдайда операцияның жалпы саны M=n log N n болады. |