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

Որքա՞ն են տարբերվում արագ տեսակավորման վատագույն ու միջին դեպքերի աշխատելու ժամանակները։ Արի նայենք վատագույն աշխատելու ժամանակին։ Պատկերացրու՝ մենք անբախտ ենք, ու մեր մասնատման չափերն անհավասարակշիռ են։ Ընդունենք, որ partition ֆունկցիայով ընտրված հենակետը միշտ$n$n տարր ունեցող ենթազանգվածի կամ ամենամեծ, կամ ամենափոքր տարրն է։ Այդ դեպքում մասնատումներից մեկը չի ունենա ոչ մի տարր, իսկ մյուսը՝ $n-1$n, minus, 1 տարր, այսինքն՝ բոլորը, բացի հենակետից։ Հետևաբար, ռեկուրենտ կանչերը կլինեն 0 ու $n-1$n, minus, 1 չափս ունեցող ենթազանգվածների վրա։

Ինչպես միացման տեսակավորման մեջ, $n$n տարր ունեցող ենթազանգվածի վրա ռեկուրենտ կանչի ժամանակը $\Theta(n)$\Theta, left parenthesis, n, right parenthesis է։ Միացման տեսակավորման մեջ դա միավորելու ժամանակն էր, արագ տեսակավորման մեջ դա բաժանելու ժամանակն է։

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

Բոլոր մակարդակների բաժանման ժամանակները գումարելով՝ կստանանք՝

Վերջին տողը ստանում ենք նրանից, որ $1 + 2 + 3 + \cdots + n$1, plus, 2, plus, 3, plus, \@cdots, plus, n-ը թվաբանական պրոգրեսիա է, որի բանաձևը ստացանք ընտրական տեսակավորումն անցնելիս (Հանում ենք 1, որովհետև արագ տեսակավորման ժամանակ գումարը սկսում է 2-ից, ոչ թե 1-ից)։ Ունենք մի քանի ցածր աստիճանով անդամներ ու հաստատուն գործակիցներ, բայց երբ օգտագործում ենք big-Θ նշագրումը, դրանք անտեսում ենք։ big-Θ նշագրման մեջ արագ տեսակավորման վատագույն աշխատելու ժամանակը $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis է։

Արագ տեսակավորման լավագույն աշխատելու ժամանակն այն դեպքում է, երբ բաժանումների չափսերը հավասար են կամ մեկը մյուսից մեծ է 1-ով։ Առաջին դեպքը լինում է այն ժամանակ, երբ ենթազանգվածն ունի կենտ թվով տարրեր, ու հենակետն ընկնում է ուղիղ մեջտեղում, և ամեն բաժանումն ունի $(n-1)/2$left parenthesis, n, minus, 1, right parenthesis, slash, 2 տարր։ Երկրորդ դեպքը լինում է այն ժամանակ, երբ ենթազանգվածն ունի զույգ $n$n թվով տարրեր, և մի բաժանումն ունի $n/2$n, slash, 2 տարր, իսկ մյուսը՝ $n/2-1$n, slash, 2, minus, 1։ Այս դեպքերից յուրաքանչյուրում ամեն բաժանումն ունի առավելագույնը $n/2$n, slash, 2 տարր, և ենթախնդիրների չափսերի ծառը շատ նման է միացման տեսակավորման ենթախնդիրների չափսերի ծառին, և բաժանումների ժամանակները համարյա հավասար են միավորումների ժամանակներին․

big-Θ նշագրումն օգտագործելով ստանում ենք նույն արդյունքը, ինչ միացման տեսակավորման ժամանակ՝ $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis։

Ցույց տալու համար, որ միջին աշխատելու ժամանակը նույնպես $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis է, մեզնից բավականին խորացված մաթեմատիկա կպահանջվի, հետևաբար դրան չենք անդրադառնա։ Սակայն մի քանի օրինակով կարող ենք պատկերացում կազմել, թե ինչու է այն $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis (Երբ ունենք $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, դրանից հետևում է $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis սահմանը, քանի որ միջին աշխատելու ժամանակը չի կարող ամենալավ աշխատելու ժամանակից ավելի լավը լինել)։ Սկզբում արի պատրեկացնենք, որ չենք ստանում հավասար բաժանումներ, սակայն վատագույն դեպքում դրանց հարաբերակցությունը լինում է 3-ը 1-ի։ Այսինքն՝ պատկերացրու, եթե ամեն բաժանումից հետո $3n/4$3, n, slash, 4 տարրերն ընկնում են մի կողմում, իսկ $n/4$n, slash, 4 տարրերը՝ մյուս կողմում (Մաթեմատիկական հաշվարկները չպղտորելու համար արի մի պահ մոռանանք հենակետի մասին)։ Այս դեպքում ենթախնդիրների չափսերի ծառն այսպիսի տեսք կունենա.

Ամեն մի հանգույցի ձախ երեխան ենթախնդրի 1/4 չափն ունի, իսկ աջ երեխան՝ 3/4 չափը։ Քանի որ փոքր ենթախնդիրները ձախ կողմում են, ապա ձախ կողմով իջնելով ավելի կարճ ժամանակում կհասնենք 1 չափի ենթախնդրին։ Ինչպես գրաֆիկն է ցույց տալիս, $\log_4 n$log, start base, 4, end base, n մակարդակ անցնելուց հետո հասնում ենք 1\ չափի ենթախնդրի։ Ինչո՞ւ հենց $\log_4 n$log, start base, 4, end base, n մակարդակ։ Հեշտ տարբերակ կլինի վերցնել 1-ն ու անընդհատ այն բազմապատկել 4-ով, մինչև կհասնենք $n$n-ին։ Այլ կերպ ասած՝ մենք փորձում ենք գտնել, թե $x$x-ի ո՞ր արժեքի դեպքում է $4^x = n$4, start superscript, x, end superscript, equals, n։ Պատասխանն է՝ $\log_4 n$log, start base, 4, end base, n։ Իսկ ի՞նչ կլինի, եթե գնանք աջ երեխաների ճանապարհով։ Ինչպես գրաֆիկն է ցույց տալիս, $\log_{4/3} n$log, start base, 4, slash, 3, end base, n մակարդակ անցնելուց հետո հասնում ենք 1\ չափի ենթախնդրի։ Ինչո՞ւ հենց $\log_{4/3} n$log, start base, 4, slash, 3, end base, n մակարդակ։ Քանի որ ամեն աջ երեխան իր վերևում ընկած հանգույցի (ծնող հանգույցի) 3/4 չափն է, ապա ամեն ծնողն իր աջ երեխայի 4/3 չափն է։ Արի նորից սկսենք 1 չափով ենթախնդրից ու անընդհատ բազմապատկենք 4/3-ով, մինչև կհասնենք $n$n-ին։ $x$x-ի ո՞ր արժեքի դեպքում է $(4/3)^x = n$left parenthesis, 4, slash, 3, right parenthesis, start superscript, x, end superscript, equals, n։ Պատասխանն է՝ $\log_{4/3} n$log, start base, 4, slash, 3, end base, n։

Առաջին $\log_4 n$log, start base, 4, end base, n մակարդակներից յուրաքանչյուրում կա $n$n հանգույց (նորից մի պահ մոռանում ենք հենակետի մասին), հետևաբար դրանց բաժանման ժամանակները կլինեն $cn$c, n։ Իսկ մյուս մակարդակներո՞ւմ։ Ամեն մակարդակն ունի n-ից քիչ հանգույցներ, հետևաբար ամեն մակարդակի բաժանման ժամանակն առավելագույնը $cn$c, n է։ Ընդհանուր կա $\log_{4/3} n$log, start base, 4, slash, 3, end base, n մակարդակ, և ընդհանուր բաժանման ժամանակը $O(n \log_{4/3} n)$O, left parenthesis, n, log, start base, 4, slash, 3, end base, n, right parenthesis է։ Հիմա կա մաթեմատիկական փաստ, որ

բոլոր $a$a, $b$b և $n$n դրական թվերի համար։ Տեղադրելով $a = 4/3$a, equals, 4, slash, 3 և $b = 2$b, equals, 2՝ ստանում ենք

և հետևաբար $\log_{4/3} n$log, start base, 4, slash, 3, end base, n-ն ու $\log_2 n$log, start base, 2, end base, n-ը միայն տարբերվում են $\log_2 (4/3)$log, start base, 2, end base, left parenthesis, 4, slash, 3, right parenthesis-ի գործակցով, որը հաստատուն է։ Քանի որ big-O նշագրման մեջ գործակիցները դեր չունեն, կարող ենք ասել, որ եթե բաժանումները 3-ը 1-ի հարաբերակցությունն ունեն, ապա արագ տեսակավորման աշխատելու ժամանակը $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis է, որն ուղղակի ավելի մեծ հաստատուն գործակից ունի, քան լավագույն դեպքի աշխատելու ժամանակը։

Որքա՞ն հաճախ ենք տեսնում 3-ը 1-ի կամ ավելի լավ հարաբերակցության բաժանումներ։ Կախված է, թե ինչպես ենք ընտրում հենակետը։ Պատկերացնենք, թե հենակետը բաժանումից հետո հավասարապես կարող է հայտնվել $n$n տարր ունեցող ենթազանգվածի յուրաքանչյուր մասում։ Հետևաբար, 3-ը 1-ի կամ ավելի լավ հարաբերակցության բաժանումներ ստանալու համար պետք է հենակետը լինի «մեջտեղի կեսում» ինչ-որ տեղ:

Հետևաբար, եթե հենակետը հավասարապես կարող է հայտնվել ենթազանգվածի յուրաքանչյուր կետում, կա վատագույնս 3-ը 1-ի բաժանում ստանալու 50% հավանականություն։ Այլ կերպ ասած՝ մենք սպասում ենք 3-ը 1-ի կամ ավելի լավ հարաբերակություն ունեցող բաժանում դեպքերի ուղիղ կեսում։

Հասկանալու համար, թե ինչպես է արագ տեսակավորման միջին դեպքի աշխատելու ժամանակը $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, կդիտարկենք այն օրինակը, որտեղ դեպքերի կեսում չենք ստանում 3-ը 1-ի բաժանում, այլ ստանում ենք վատագույն դեպքի բաժանում։ Պատկերացնենք, թե 3-ը 1-ի բաժանումն ու վատագույն բաժանումը լինում են մեկումեջ, և վերցնենք ծառի վրա հանգույց, որի ենթազանգվածն ունի $k$k տարր։ Կտեսնենք, որ ծառն այսպիսի տեսքի է․

ոչ թե այսպիսի՝

Հետևաբար, երբ դեպքերի կեսում ստանում ենք վատագույն դեպք, կեսում՝ 3-ը 1-ի կամ ավելի լավ դեպք, աշխատելու ժամանակը կլինի ամբողջովին 3-ը 1-ի աշխատելու ժամանակի կրկնակին։ Նորից հիշենք, որ դա ուղղակի հաստատուն գործակից է, և big-O նշագրման մեջ դրա մասին մոռանում ենք, հետևաբար մեր դեպքում, երբ մեկումեջ ստանում ենք վատագույն ու 3-ը 1-ի բաժանումներ, աշխատելու ժամանակը $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis է։

Նկատի ունեցիր, որ այս վերլուծությունը մաթեմատիկորեն ճշգրիտ չէ, բայց տալիս է մոտավոր պատկերացում, թե ինչու էաշխատելու միջին ժամանակը $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis։

Պատկերացնենք, իբր քո վատագույն թշնամին քեզ տվել է զանգված, որը պետք է տեսակավորես արագ տեսակավորմամբ, և նա գիտի, որ միշտ ամենաաջ տարրն ես ընտրում որպես հենակետ, ու հետևաբար այնպես է զանգվածը դասավորել, որ դու միշտ ստանաս վատագույն դեպքի բաժանում։ Ինչպե՞ս կարող ես հիմարեցնել քո թշնամուն։

Պարտադիր չէ բոլոր ենթազանգվածներում ամենաաջ տարրն ընտրել որպես ենթազանգված։ Փոխարենը ամեն ենթազանգվածում կարող ես հենակետ ընտրել պատահականության սկզբունքով։ Բայց մի րոպե․ partition ֆունկցիան դեռ կարծում է, թե ամենաաջ տարրն է մեր ենթազանգվածի հենակետը։ Ոչ մի խնդիր․ ուղղակի քո ընտրած հենակետն ամենաաջ տարրի հետ տեղերով փոխիր և կատարիր բաժանումներն այնպես, ինչպես անում էիր։ Դու այս դեպքում պատվով դուրս կգաս թշնամուդ յուրաքանչյուր չար կատակի տակից, եթե, իհարկե, ինչ-որ հրաշքով նա նախապես բոլոր պատահական ընտրված հենակետերը չգուշակի։

Իրականում մի փոքր փոփոխելով կարող ես վատագույնը 3-ը 1-ի հարաբերակցության բաժանում ստանալու հնարավորություններդ մեծացնել։ Պատահականության սկզբունքով ընտրիր ոչ թե մեկ, այլ երեք տարր և դրանց մեդիանը դարձրու հենակետը (այն ամենաաջ տարրի հետ տեղերով փոխելով)։ Մեդիան ասելով նկատի ունենք այն թիվը, որը գտնվում է երեք տարրի մեջտեղում։ Քեզ ցույց չենք տա՝ ինչպես, բայց եթե ընտրում ես երեք պատահաբար ընտրված տարրերի մեդիանը, ունես 3-ը 1-ի կամ ավելի լավ բաժանում ստանալու 68,75% հնարավորություն (11/16)։ Նույնիսկ ավելի կարող ես խորանալ։ Եթե ընտրես հինգ տարր, ու դրանց մեդիանը լինի քո հենակետը, վատագույնը 3-ը 1-ի բաժանում ստանալու հավանականությունը դառնում է մոտ 79,3% (203/256)։ Եթե ընտրես յոթ տարր, ու դրանց մեդիանը լինի քո հենակետը, վատագույնը 3-ը 1-ի բաժանում ստանալու հավանականությունը դառնում է մոտ 85,9% (1759/2048): Իննի մեդիա՞նը։ Մոտ 90,2% (59123/65536)։ 11-ի մեդիա՞նը։ Մոտ 93,1% (488293/524288)։ Մոտավոր պատկերացրիր։ Իհարկե, պարտադիր չէ ընտրել տարրերի մեծ քանակություն և վերցնել դրանց մեդիանը, քանի որ դա կարող է ազդել աշխատելու ժամանակի վրա։

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