If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

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

Քանի որ merge ֆունկցիան աշխատում է Θ(n) ժամանակում, երբ միացնում ենք n տարր, ինչպե՞ս կարող ենք ցույց տալ, որ mergeSort-ն աշխատում է Θ(nlog2n) ժամանակում։ Սկսում ենք «Բաժանիր և տիրիր» ալգորիթմի երեք մասից։ Վերցնում ենք n տարր ունեցող զանգված և պատկերացնում, թե տեսակավորում ենք։
  1. Բաժանելու քայլն ունի հաստատուն ժամանակ՝ անկախ ենթազանգվածի չափսից։ Ի վերջո, բաժանելու քայլը միայն գտնում է q ցուցիչը, որը p և r ցուցիչների միջնակետն է։ Հիշիր, որ big-Θ նշագրման մեջ հաստատուն ժամանակը գրում ենք Θ(1)։
  2. Տիրելու քայլում ռեկուրսիվորեն տեսակավորում ենք երկու ենթազանգված, որոնցից յուրաքանչյուրն ունի n/2 տարր։ Սա տևում է ինչ-որ ժամանակ, որը հաշվի կառնենք ենթազանգվածների ժամանակ։
  3. Միավորելու քայլը միավորում է n տարր Θ(n) ժամանակում։
Եթե բաժանելու և միավորելու քայլերը միասին վերցնենք, բաժանելու Θ(1) աշխատելու ժամանակը միավորելու աշխատելու ժամանակի՝ Θ(n)-ի հետ համեմատելիս կդառնա ցածր աստիճանով անդամը։ Հետևաբար, արի այդ երկու քայլերը վերցնենք միասին և ասենք, որ դրանց աշխատելու ժամանակը Θ(n) է։ Ավելի պարզ լինելու համար արի ասենք, որ բաժանելու և միավորելու քայլերը միասին cn ժամանակում են աշխատում ինչ-որ c հաստատուն թվի համար։
Ամեն ինչ պարզ հասկանալու համար արի ենթադրենք, որ եթե n>1, ապա n-ը միշտ զույգ է, որ n/2-ն էլ լինի ամբողջ թիվ (Հաշվի առնելով, որ կենտ n-երի դեպքում արժեքը big-Θ նշագրման մեջ չի փոխվի)։ Հետևաբար, mergeSort-ի աշխատելու ժամանակը n տարր ունեցող ենթազանգվածի համար mergeSort-ի աշխատելու ժամանակը կլինի (n/2) տարր ունեցող ենթազանգվածի կրկնապատիկի գումարը (տիրելու քայլը)՝ գումարած cn (բաժանելու և միացնելու քայլը)։
Հիմա արի հասկանանք, թե որքան է n/2 տարրի վրա երկու ռեկուրենտ կանչերի աշխատելու ժամանակը։ Այս կանչերից յուրաքանչյուրի աշխատելու ժամանակը mergeSort-ի՝ (n/4) տարրերով ենթազանգվածի աշխատելու ժամանակի կրկնապատիկն է (քանի որ պետք է կիսենք n/2-ը) գումարած cn/2 միավորելու համար։ Մենք ունենք n/2 չափով երկու ենթախնդիր, և դրանցից յուրաքանչյուրը միավորվում է cn/2 ժամանակում, հետևաբար n/2 չափով ենթախնդիրները միավորելու համար մեր ծախսած ընդհանուր ժամանակը 2cn/2=cn է։
Արի միավորելու ժամանակները նկարենք ծառի վրա․
Ծրագրավորողները ծառերը նկարում են գլխիվայր։ Ծառը գրաֆիկ է, որը չունի ցիկլեր (ճանապարհներ, որոնք սկսվում և ավարտվում են նույն տեղում)։ Ծառի գագաթներն ընդունված է անվանել հանգույցներ։ Արմատ հանգույցը վերևում է․ այստեղ արմատը n ենթազանգվածն է, որը n տարր ունեցող զանգված է։ Արմատի ներքևում կան երկու երեխա հանգույցներ՝ յուրաքանչյուրի դիմաց գրված n/2, որը ցույց է տալիս երկու ենթախնդիրների ենթազանգվածները՝ n/2 չափի։
Ամեն n/2 չափի ենթախնդիրը ռեկուրսիվորեն տեսակավորում է երկու (n/2)/2 կամ n/4 չափի ենթազանգված։ Քանի որ երկու n/2 չափի ենթախնդիր, կա չորս n/4 չափի ենթախնդիրկա, այդ չորս ենթախնդիրները միավորվում են՝ n/4, հետևաբար ամեն ենթախնդրի միավորման ժամանակը cn/4 է։ Գումարելով բոլոր չորս ենթախնդիրները՝ տեսնում ենք, որ ընդհանուր բոլոր n/4 չափի ենթախնդիրների միավորման ժամանակը 4cn/4=cn է․
Ի՞նչ ես կարծում, ի՞նչ կլինի n/8 չափի ենթախնդիրների դեպքում։ Դրանք կլինեն ութ հատ, և յուրաքանչյուրի միավորման ժամանակը կլինի cn/8, այսինքն՝ ընդհանուր 8cn/8=cn
Որքան ենթախնդիրները փոքրանում են, դրանց քանակը կրկնապատկվում է ռեկուրսիայի հաջորդ մակարդակում, իսկ միավորման ժամանակը կիսվում է։ Կրկնապատկվելն ու կիսվելն իրար չեղարկում են, հետևաբար ռեկուրսիայի բոլոր մակարդակներում միավորման ժամանակը cn է։ Ի վերջո հասնում ենք 1 չափով ենթախնդիրներին՝ առաջնային դեպքին։ 1 չափով ենթազանգվածները տեսակավորվում են Θ(1) ժամանակում, որովհետև ստուգում ենք p<r պայմանը, և սա ժամանակ է տանում։ Քանի՞ 1 չափի ենթազանգված կա այստեղ։ Քանի որ սկսել ենք n տարրից, պետք է n ենթազանգված լինի։ Քանի որ առաջնային դեպքերից յուրաքանչյուրն ունի Θ(1) ժամանակ, ամբողջ առաջնային դեպքն ունի cn ժամանակ․
Հիմա գիտենք, թե որքան ժամանակում է ամեն չափի ենթախնդիրը կատարում միավորվումը։ mergeSort-ի ընդհանուր ժամանակը բոլոր մակարդակների միավորման ժամանակների գումարն է։ Եթե ծառի վրա ունենք l մակարդակ, ապա ընդհանուր միավորման ժամանակը lcn է։ Ուրեմն ի՞նչ է l-ը։ Մենք սկսում ենք n չափի ենթախնդիրներից ու շարունակաբար կիսում դրանք, մինչև կհասնենք 1\ չափի ենթախնդիրների։ Տեսանք, որ երկուական որոնման մեջ l=log2n+1։ Օրինակ, եթե n=8, ապա log2n+1=4, և իրոք, ծառն ունի չորս մակարդակ՝ n=8,4,2,1։ Հետևաբար, mergeSort-ի ընդհանուր ժամանակը cn(log2n+1) է։ Աշխատելու ժամանակը ցույց տալու համար big-Θ նշագրումն օգտագործելիս կարող ենք անտեսել ցածր աստիճանով անդամը (+1) և հաստատուն գործակիցը (c) և կստանանք Θ(nlog2n) աշխատելու ժամանակ։
Միացման տեսակավորման մասին մեկ այլ կարևոր բան էլ պետք է նկատի ունենալ։ Միավորելու ժամանակ այն պատճենում է ամբողջ զանգվածը, հետո կիսում այն, մի կեսը lowHalf, իսկ մյուսը՝ highHalf։ Քանի որ այն պատճենում է ավելի քան հաստատուն քանակի տարրեր, ասում ենք, որ միացման տեսակավորումը տեղում չի աշխատում։ Որպես համեմատություն կարող ենք ասել, որ ընտրական տեսակավորումն ու ներդրման տեսակավորումն աշխատում են տեղում, քանի որ դրանք չեն պատճենում զանգվածը ավելի քան հաստատուն քանակի տարրերի համար։ Ծրագրավորողները սիրում են իմանալ՝ արդյոք ալգորիթմն աշխատում է տեղում, թե ոչ, որովհետև որոշ համակարգերում նախընտրելի են տեղում աշխատող ալգորիթմները։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: