Бөліп ал да басқар” принципіне негізделген алгоритмдерді талдау

Егер алгоритм өз өзіне рекурсивті бұрылса оның жұмыс уақыты рекурентті теңдеумен немесе рекурентті байланыс көмегімен сипатталады. Мұнда n кіріс көлемі бар есептің барлығын шешу үшін қажетті толық уақыт қосымша есептерді шешуге кететін уақыт арқылы сипатталады. Кейін осы рекурентті теңдеу белгілі бір математикалық әдістердің көмегімен шешіледі және алгоритмнің өнімділігінң шекаралары қойылады.

“Бөліп ал да басқар” принципіне негізделген алгоритм уақыты үшін рекуренттік байланысты алу 3этапқа негізделеді. T(n) арқыты өлшемі n-ге тең есепті шешу уақытын белгілейміз. Егер есептің өлшемі жеткілікті аз болса, айталық n<=c, мұнда c- кейбір алдын ала белгілі константа, онда есеп белгілі бір Θ(1) (тета)нақтыланған уақытта шешіледі. Есеп а кіші есептерге бөлінеді десек, олардың көлемі берілген есептің көлемінің 1/b бөлшегіне тең. Егер есепті қосымша есептерге бөлу уақыты D(n) уақыт аралығында болса, ал кіші есептердің шешімін бастапқы есептің шешіміне біріктіру уақыты C(n) уақытына тең болса, төмендегідей рекуреттік байланысты аламыз:

Біріктіріп сұрыптау алгоритмін талдау

Бұл алгоритм сұрыпталатын элементтердің еркін санына дұрыс жұмыс істейді. Дегенмен егер бастапқы есептің элементтер саны екінің дәрежесіне тең болса, онда рекурентті теңдеудің талдауы оңайланады. Бұл жағдайда бөлудің әрбір қадамында екі ішкі тізбектер алынады, олардың өлшемі дәл n/2 –ге тең болады.

n санды сұрыптайтын алгоритмнің T(n) жұмыс уақытының жоғарғы бағасы үшін рекурентті теңдеу алу үшін төмендегідей пайымдаймыз. Біріктіру әдісімен бір элементті сұрыптау нақты уақыт ішінде жасалады. Егер n>1, жұмыс уақыты төмендегідей бөлінеді.

Бөлу: Бөлу барысында ішкімассивтің ортасы анықталады. Бұл операция нақты уақытқа созылады, сондықтан D(n) =Θ(1).

Бағындыру: көлемі n/2 –ге тең екі ішкі есеп рекурсивті шешіледі. Бұл ішкіесептерді шешу уақыты 2Т(n/2) –ге тең.

Қосу(комбинирование): біріктіру процедурасы n-элементті ішкі массивте Θ(n) уақытта орындалады, сондықтан C(n)= Θ(n).

D(n) және C(n) функцияларын қосып Θ(n) және Θ(1) шамаларының қосындысын аламыз, ол сызықтық функция болып табылады, яғни Θ(n) б ұл шамаға 2Т(n/2) – ні қосып бағындыру этабына сәйке с ең нашар жағдайдағы біріктіру әдісі бойынша сұраптау алгоритмініңT(n) жұмыс уақыты үшін рекурентті байланыс аламыз

1. В-ағаштар.

Б-ағаштары дегеніміз- магниттік дискіде немесе тікелей жеткізілетін құралдарда ақпаратты сақтауды қамтамасыз ететін теңестірілген ағаштардың бір түрі. Б-ағаштары қызыл–қара ағаштарға ұқсайды.Айырмашылығы мынада: қолданылатын дисктің мінездемесіне қарай Б-ағаштарының бөліктерінде көп бала, іс жүзінде мыңға дейін болуы мүмкін.Осыған байланысты ағаштың биіктігі O (log n)-ді бағалау нәтижесі бойынша қызыл–қара ағаштарға қарағанда айтарлықтай аз мөлшерде. Қызыл–қара ағаштар сияқты Б-ағаштары да O (log n) мерзімінде көптеген n өлшемдегі әр қилы операцияларды жүзеге асыра алады. x түйіншегі, сақта- n[x] кілттердің, n имеет[x] + 1 бала-шағалардың. x кілттерге деген сақтал- қызмет ет- барлық оның бұтақтарын бас n бөлетін шекаралармен[x] + 1 топтардың; үшін бас-басы топты бір x бала-шағаларынан жауап береді. ізденісте Б-ағашта біз кілтті пен n салыстырамыз[x] ара x сақталатын кілттермен, қарамастан және нәтижені салыстырамыз.

Б-ағаштарымен жүргізілетін негізгі операциялар. Б-ағашының тамыры әрқашанда оперативті есте болады деп санауға болады,өйткені дисктен оқу операциясы тамыр үшін қажет етілмейді; дегенмен де біз ылғи да тамырды өзгерткенде, дискте сақтауымыз керек.