Мундарижа Кириш

MergeLists алгоритми таҳлили
Элементларни солиштириш билан фақат MergeLists процедураси шуғулланади, шунинг учун унинг таҳлилидан бошлаймиз. А рўйхат барча элементлари В рўйхат элементларидан кичик бўлган ҳолни қараймиз. MergeLists процедураси нима қилади? У А[1] ва В[1] элементларни солиштиради ва А[1] элемент кичиклигидан С рўйхатга кўчирилади. Кейин А[2] ва В[1] элементлар солиштирилади ва кичик А[2] элемент С рўйхатга кўчирилади. А рўйхат барча элементларини B[1] билан солиштириш жараёни рўйхат охиригача такрорланади. Бу шуни билдирадики, алгоритм N_A солиштириш бажаради, бунда N_A билан А рўйхатдаги элементлар сони белгиланган. Аксинча, агар В рўйхат барча элементлари А рўйхат элементларидан кичик бўлса, у ҳолда солиштиришлар сони N_B га, яъни В рўйхат элементлари сонига тенг бўлади.
Агар А рўйхатнинг биринчи элементи В рўйхатнинг биринчи элементидан катта, лекин А рўйхатнинг барча элементлари В рўйхатнинг иккинчи элементидан кичик бўлса нима бўлади? У ҳолда биз А[1] ва В[1] ларни солиштирамиз, В[1] элементни С рўйхатга кўчирамиз ва А рўйхат ҳар бир элементини В[2] билан солиштиргандан сўнг уни С га кўчирамиз. Бу ҳолда барча солиштиришлар сони N_A + 1 га тенг бўлади. Бошқа юқорида тавсифланган каби ҳолларда энг яхши ҳолат юз беради.
Биз кўрдикки агар А рўйхатнинг барча элементлари B[1] ва _-В [2] элементлар орасида бўлса, солиштиришлар сони А рўйхат барча элементлар В рўйхат элементларидан кичик бўлган ҳолдаги солиштиришлар сонидан кўп бўлади. Агар А ва В рўйхат элементлари қийматлари «бирин-кетин» жойлашган бўлса нима бўлишини қараймиз. Бошқача айтганда, агар А[1] элемент В[1] ва В[2] орасида жойлашса, А[2] элемент В[2] ва В[3] лар орасида жойлашса, А[3] элемент В[3] ва В[4] орасида ва ҳ.к. жойлашса нима бўлади. Натижада ҳар бир солиштиришда А ёки В рўйхатлардан бирининг элементи С га кўчирилади. Бу тартиблашда А рўйхатнинг охирги элементидан ташқари икки тўпламдаги барча элементлар бирин кетин кўчирилади. Натижада бу энг ёмон ҳол солиштиришлари N_A+N_B-1 га тенг.