Ներդրման տեսակավորում. վերլուծություն

Ինչպես ընտրական տեսակավորումը, ներդրման տեսակավորումն անցնում է զանգվածի ցուցիչների վրայով։ Այն $1,2,3,\dots ,n-1$‍ ցուցիչներով տարրերի վրա կանչում է insert ֆունկցիան։ Ինչպես indexOfMinimum-ի ամեն կանչի ժամանակն է կախված տեսակավորված ենթազանգվածի չափսից, այնպես էլ ամեն insert ֆունկցիայի կանչի ժամանակը։ Իրականում վերջինս կարող է և կախված չլինել, և կտեսնենք՝ ինչու։

Արի վերցնենք այն դեպքը, երբ կանչում ենք insert ֆունկցիան, և ենթազանգվածում տեղադրվող արժեքը փոքր է իրենից ձախ բոլոր արժեքներից։ Օրինակ, եթե [2, 3, 5, 7, 11] ենթազանգվածի մեջ տեղադրենք 0, ապա ենթազանգվածի բոլոր տարրերը պետք է մեկով տեղափոխվեն դեպի աջ։ Հետևաբար, եթե տեղադրում ենք $k$‍ տարր ունեցող ենթազանգվածում, հնարավոր է, որ բոլոր $k$‍ տարրերը տեղափոխվեն մեկով աջ։ Կոդի տողերը հաշվելու փոխարեն կարող ենք դրա ժամանակը նշանակել հաստատուն թվով՝ $c$‍-ով։ Հետևաբար, ընդհուպ մինչև $c\cdot k$‍ ժամանակում տարր կտեղադրենք $k$‍ տարրերով ենթազանգվածում։

Պատկերացրու՝ ամեն insert-ի կանչի ժամանակ արժեքը փոքր է իրենից ձախ բոլոր արժեքներից։ insert-ի առաջին կանչի ժամանակ $k=1$‍։ Երկրորդ անգամ $k=2$‍։ Երրորդ անգամ $k=3$‍։ Եվ այդպես շարունակ, մինչև $k=n-1$‍։ Հետևաբար, տեսակավորված ենթազանգվածում տարր տեղադրելու ընդհանուր ժամանակը հավասար է՝

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

Գումարը թվաբանական պրոգրեսիա է, բայց մեկից մինչև $n-1$‍ թվերի համար, ոչ թե $n$‍։ Օգտագործելով թվաբանական պրոգրեսիայի գումարի բանաձևը՝ տեղադրելու ընդհանուր ժամանակը ստանում ենք՝

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

big-Θ նշագրումով ազատվում ենք ցածր աստիճանով անդամից՝ $cn/2$‍, և հաստատուն գործակիցներից՝ $c$‍ ու 1/2՝ արդյունքում ստանալով ներդրման տեսակավորման աշխատելու ժամանակը՝ $\mathrm{\Theta }(n^2)$‍։

Կարո՞ղ է ներդրման տեսակավորման ժամանակը լինել ավելի քիչ, քան $\mathrm{\Theta }(n^2)$‍։ Պատասխանն է՝ այո։ Պատկերացրու՝ ունենք [2, 3, 5, 7, 11] զանգված, որտեղ առաջին չորս տարրերը տեսակավորված են, և մենք տեղադրում ենք 11\ թիվը։ Առաջին համեմատության ժամանակ տեսնում ենք, որ 11-ը մեծ է 7-ից, և ենթազանգվածի ոչ մի տարր չենք տեղափոխում աջ։ insert-ի այս կանչն ունի հաստատուն ժամանակ։ Պատկերացրու, եթե ամեն insert կանչի ժամանակը լինի հաստատուն։ Քանի որ ընդհանուր կա $n-1$‍ insert կանչ, եթե դրանցից յուրաքանչյուրի կանչն ունենա հաստատուն $c$‍ ժամանակ, ապա ներդրման տեսակավորման ընդհանուր ժամանակը կլինի $c\cdot (n-1)$‍, որը $\mathrm{\Theta }(n)$‍ է, ոչ թե $\mathrm{\Theta }(n^2)$‍։

Կարո՞ղ են այս դեպքերը հանդիպել մեզ։ Կարո՞ղ է insert-ի ամեն կանչ ենթազանգվածի բոլոր տարրերը մեկով շարժել դեպի աջ։ Կարո՞ղ է insert-ի ոչ մի կանչ տարր չտեղաշարժի։ Երկուսն էլ հնարավոր է։ insert կանչից հետո բանալուց ձախ ենթազանգվածում դրանից մեծ բոլոր թվերը մեկով տեղաշարժվում են դեպի աջ։ Հետևաբար, եթե բոլոր տարրերը փոքր են իրենցից ձախ գտնվող բոլոր տարրերից, ապա ներդրման տեսակավորման աշխատելու ժամանակը $\mathrm{\Theta }(n^2)$‍ է։ Ի՞նչ է նշանակում բոլոր տարրերը փոքր են իրենցից ձախ գտնվող բոլոր տարրերից։ Նշանակում է, որ զանգվածն ամենասկզբում հակառակ դասավորվածությունն ուներ, այսինքն՝ օրինակ [11, 7, 5, 3, 2]։ Հետևաբար, հակառակ դասավորված զանգվածը ներդրման տեսակավորման վատագույն դեպքն է։

Իսկ ի՞նչ կլինի մյուս դեպքում։ Եթե insert կանչի ժամանակ ոչ մի տարր չի տեղաշարժվել, ապա բանալին մեծ է իրենից ձախ բոլոր տարրերից։ Հետևաբար, եթե բոլոր տարրերը մեծ կամ հավասար են իրենցից ձախ գտնվող բոլոր տարրերին, ապա ներդրման տեսակավորման աշխատելու ժամանակը $\mathrm{\Theta }(n)$‍ է։ Այս դեպքը տեղի է ունենում այն ժամանակ, երբ սկզբում արդեն զանգվածը ճիշտ դասավորված է, և հետևաբար ներդրման տեսակավորման լավագույն դեպքն արդեն տեսակավորված զանգվածն է։

Է՞լ ինչ կարող ենք ասել ներդրման տեսակավորման աշխատելու ժամանակի մասին։ Ենթադրենք՝ զանգվածը խառն է դասավորված։ Ապա միջինում կակնկալենք, որյուրաքանչյուր տարրը փոքր լինի իրենից ձախ տարրերից կեսից։ Այս դեպքում $k$‍ տարրերով ենթազանգվածի վրա insert կանչը միջինում դրանցից $k/2$‍-ը կտեղափոխի մեկով աջ։ Աշխատելու ժամանակը կլինի վատագույն աշխատելու ժամանակի կեսը։ Բայց ասիմպտոտային նշագրման ժամանակ, երբ հաստատուն գործակիցներն անտեսում ենք, միջին դեպքը կլինի $\mathrm{\Theta }(n^2)$‍՝ վատագույն դեպքի նման։

Իսկ ի՞նչ կլինի, եթե զանգվածը «համարյա տեսակավորված է»․ յուրաքանչյուր տարրը վատագույն դեպքում անցնում է հաստատուն տարրերի վրայով, ասենք՝ 17։ Հետևաբար, insert-ի ամեն կանչ տեղափոխում է առավելագույնը 17 տարր, և $k$‍ տարր ունեցող ենթազանգվածի վրա insert-ի մի կանչի ժամանակը կլինի առավելագույնը $17\cdot c$‍։ $n-1$‍ հատ insert կանչից հետո աշխատելու ժամանակը կլինի $17\cdot c\cdot (n-1)$‍, որը $\mathrm{\Theta }(n)$‍-ն է, ճիշտ այնպես, ինչպես լավագույն դեպքում։ Հետևաբար, ներդրման տեսակավորումն արագ է, երբ ունենք համարյա տեսակավորված զանգված։

Որպես ներդրման տեսակավորման աշխատելու ժամանակների ամփոփում՝

Եթե ուզում ես բոլոր դեպքերի համար սահմանել ներդրման տեսակավորման աշխատելու ժամանակը, ապա պետք է ասես, որ այն $O(n^2)$‍ է։ Չես կարող ասել $\mathrm{\Theta }(n^2)$‍, քանի որ լավագույն դեպքը $\mathrm{\Theta }(n)$‍ է։ Չես կարող ասել $\mathrm{\Theta }(n)$‍, քանի որ վատագույն դեպքը $\mathrm{\Theta }(n^2)$‍ է։

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