Միացման տեսակավորում. վերլուծություն

Քանի որ merge ֆունկցիան աշխատում է $\Theta(n)$\Theta, left parenthesis, n, right parenthesis ժամանակում, երբ միացնում ենք $n$n տարր, ինչպե՞ս կարող ենք ցույց տալ, որ mergeSort-ն աշխատում է $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis ժամանակում։ Սկսում ենք «Բաժանիր և տիրիր» ալգորիթմի երեք մասից։ Վերցնում ենք $n$n տարր ունեցող զանգված և պատկերացնում, թե տեսակավորում ենք։

Եթե բաժանելու և միավորելու քայլերը միասին վերցնենք, բաժանելու $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis աշխատելու ժամանակը միավորելու աշխատելու ժամանակի՝ $\Theta(n)$\Theta, left parenthesis, n, right parenthesis-ի հետ համեմատելիս կդառնա ցածր աստիճանով անդամը։ Հետևաբար, արի այդ երկու քայլերը վերցնենք միասին և ասենք, որ դրանց աշխատելու ժամանակը $\Theta(n)$\Theta, left parenthesis, n, right parenthesis է։ Ավելի պարզ լինելու համար արի ասենք, որ բաժանելու և միավորելու քայլերը միասին $cn$c, n ժամանակում են աշխատում ինչ-որ $c$c հաստատուն թվի համար։

Ամեն ինչ պարզ հասկանալու համար արի ենթադրենք, որ եթե $n>1$n, is greater than, 1, ապա $n$n-ը միշտ զույգ է, որ $n/2$n, slash, 2-ն էլ լինի ամբողջ թիվ (Հաշվի առնելով, որ կենտ $n$n-երի դեպքում արժեքը big-Θ նշագրման մեջ չի փոխվի)։ Հետևաբար, mergeSort-ի աշխատելու ժամանակը $n$n տարր ունեցող ենթազանգվածի համար mergeSort-ի աշխատելու ժամանակը կլինի $(n/2)$left parenthesis, n, slash, 2, right parenthesis տարր ունեցող ենթազանգվածի կրկնապատիկի գումարը (տիրելու քայլը)՝ գումարած $cn$c, n (բաժանելու և միացնելու քայլը)։

Հիմա արի հասկանանք, թե որքան է $n/2$n, slash, 2 տարրի վրա երկու ռեկուրենտ կանչերի աշխատելու ժամանակը։ Այս կանչերից յուրաքանչյուրի աշխատելու ժամանակը mergeSort-ի՝ $(n/4)$left parenthesis, n, slash, 4, right parenthesis տարրերով ենթազանգվածի աշխատելու ժամանակի կրկնապատիկն է (քանի որ պետք է կիսենք $n/2$n, slash, 2-ը) գումարած $cn/2$c, n, slash, 2 միավորելու համար։ Մենք ունենք $n/2$n, slash, 2 չափով երկու ենթախնդիր, և դրանցից յուրաքանչյուրը միավորվում է $cn/2$c, n, slash, 2 ժամանակում, հետևաբար $n/2$n, slash, 2 չափով ենթախնդիրները միավորելու համար մեր ծախսած ընդհանուր ժամանակը $2\cdot cn/2 = cn$2, dot, c, n, slash, 2, equals, c, n է։

Արի միավորելու ժամանակները նկարենք ծառի վրա․

Ծրագրավորողները ծառերը նկարում են գլխիվայր։ Ծառը գրաֆիկ է, որը չունի ցիկլեր (ճանապարհներ, որոնք սկսվում և ավարտվում են նույն տեղում)։ Ծառի գագաթներն ընդունված է անվանել հանգույցներ։ Արմատ հանգույցը վերևում է․ այստեղ արմատը $n$n ենթազանգվածն է, որը $n$n տարր ունեցող զանգված է։ Արմատի ներքևում կան երկու երեխա հանգույցներ՝ յուրաքանչյուրի դիմաց գրված $n/2$n, slash, 2, որը ցույց է տալիս երկու ենթախնդիրների ենթազանգվածները՝ $n/2$n, slash, 2 չափի։

Ամեն $n/2$n, slash, 2 չափի ենթախնդիրը ռեկուրսիվորեն տեսակավորում է երկու $(n/2)/2$left parenthesis, n, slash, 2, right parenthesis, slash, 2 կամ $n/4$n, slash, 4 չափի ենթազանգված։ Քանի որ երկու $n/2$n, slash, 2 չափի ենթախնդիր, կա չորս $n/4$n, slash, 4 չափի ենթախնդիրկա, այդ չորս ենթախնդիրները միավորվում են՝ $n/4$n, slash, 4, հետևաբար ամեն ենթախնդրի միավորման ժամանակը $cn/4$c, n, slash, 4 է։ Գումարելով բոլոր չորս ենթախնդիրները՝ տեսնում ենք, որ ընդհանուր բոլոր $n/4$n, slash, 4 չափի ենթախնդիրների միավորման ժամանակը $4 \cdot cn/4 = cn$4, dot, c, n, slash, 4, equals, c, n է․

Ի՞նչ ես կարծում, ի՞նչ կլինի $n/8$n, slash, 8 չափի ենթախնդիրների դեպքում։ Դրանք կլինեն ութ հատ, և յուրաքանչյուրի միավորման ժամանակը կլինի $cn/8$c, n, slash, 8, այսինքն՝ ընդհանուր $8 \cdot cn/8 = cn$8, dot, c, n, slash, 8, equals, c, n․

Որքան ենթախնդիրները փոքրանում են, դրանց քանակը կրկնապատկվում է ռեկուրսիայի հաջորդ մակարդակում, իսկ միավորման ժամանակը կիսվում է։ Կրկնապատկվելն ու կիսվելն իրար չեղարկում են, հետևաբար ռեկուրսիայի բոլոր մակարդակներում միավորման ժամանակը $cn$c, n է։ Ի վերջո հասնում ենք 1 չափով ենթախնդիրներին՝ առաջնային դեպքին։ 1 չափով ենթազանգվածները տեսակավորվում են $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis ժամանակում, որովհետև ստուգում ենք $p < r$p, is less than, r պայմանը, և սա ժամանակ է տանում։ Քանի՞ 1 չափի ենթազանգված կա այստեղ։ Քանի որ սկսել ենք $n$n տարրից, պետք է $n$n ենթազանգված լինի։ Քանի որ առաջնային դեպքերից յուրաքանչյուրն ունի $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis ժամանակ, ամբողջ առաջնային դեպքն ունի $cn$c, n ժամանակ․

Հիմա գիտենք, թե որքան ժամանակում է ամեն չափի ենթախնդիրը կատարում միավորվումը։ mergeSort-ի ընդհանուր ժամանակը բոլոր մակարդակների միավորման ժամանակների գումարն է։ Եթե ծառի վրա ունենք $l$l մակարդակ, ապա ընդհանուր միավորման ժամանակը $l \cdot cn$l, dot, c, n է։ Ուրեմն ի՞նչ է $l$l-ը։ Մենք սկսում ենք $n$n չափի ենթախնդիրներից ու շարունակաբար կիսում դրանք, մինչև կհասնենք 1\ չափի ենթախնդիրների։ Տեսանք, որ երկուական որոնման մեջ $l = \log_2 n + 1$l, equals, log, start base, 2, end base, n, plus, 1։ Օրինակ, եթե $n=8$n, equals, 8, ապա $\log_2 n + 1 = 4$log, start base, 2, end base, n, plus, 1, equals, 4, և իրոք, ծառն ունի չորս մակարդակ՝ $n = 8, 4, 2, 1$n, equals, 8, comma, 4, comma, 2, comma, 1։ Հետևաբար, mergeSort-ի ընդհանուր ժամանակը $cn (\log_2 n + 1)$c, n, left parenthesis, log, start base, 2, end base, n, plus, 1, right parenthesis է։ Աշխատելու ժամանակը ցույց տալու համար big-Θ նշագրումն օգտագործելիս կարող ենք անտեսել ցածր աստիճանով անդամը ($+1$plus, 1) և հաստատուն գործակիցը ($c$c) և կստանանք $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis աշխատելու ժամանակ։

Միացման տեսակավորման մասին մեկ այլ կարևոր բան էլ պետք է նկատի ունենալ։ Միավորելու ժամանակ այն պատճենում է ամբողջ զանգվածը, հետո կիսում այն, մի կեսը lowHalf, իսկ մյուսը՝ highHalf։ Քանի որ այն պատճենում է ավելի քան հաստատուն քանակի տարրեր, ասում ենք, որ միացման տեսակավորումը տեղում չի աշխատում։ Որպես համեմատություն կարող ենք ասել, որ ընտրական տեսակավորումն ու ներդրման տեսակավորումն աշխատում են տեղում, քանի որ դրանք չեն պատճենում զանգվածը ավելի քան հաստատուն քանակի տարրերի համար։ Ծրագրավորողները սիրում են իմանալ՝ արդյոք ալգորիթմն աշխատում է տեղում, թե ոչ, որովհետև որոշ համակարգերում նախընտրելի են տեղում աշխատող ալգորիթմները։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։