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

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

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

Համակարգչային գիտություն

Դասընթաց․ (Համակարգչային գիտություն)  > Բաժին 1

Դաս 4: Ընտրական տեսակավորում
Ծրագրավորում
Համակարգչային գիտություն
Ալգորիթմներ
Ընտրական տեսակավորում
© 2023 Khan AcademyՕգտագործման պայմաններԳաղտնիության քաղաքականությունՔուքի (Cookie) ծանուցում

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

«Google Classroom»
Ընտրական տեսակավորումն անցնում է զանգվածի ցուցիչների վրայով․ ամեն ցուցչի համար ընտրական տեսակավորումը կանչում է indexOfMinimum և swap։ Եթե զանգվածի երկարությունը n է, զանգվածում կա n ցուցիչ։
Քանի որ ցիկլի մարմինն աշխատեցնում է երկու տող կոդ, հնարավոր է՝ մտածես, թե ընտրական տեսակավորումով 2, n տող կոդ է աշխատում։ Դա այդպես չէ։ Հիշիր, որ երբ indexOfMinimum և swap ֆունկցիաները կանչվում են, կոդի միայն մի հատվածն է աշխատեցվում։
Քանի՞ տող կոդ է աշխատում swap-ի կանչի ժամանակ։ Սովորաբար այն երեք տող է, հետևաբար ամեն swap կանչը լինում է հաստատուն ժամանակում։
Քանի՞ տող կոդ է աշխատում indexOfMinimum կանչի ժամանակ։ Մենք պետք է հաշվի առնենք indexOfMinimum-ի ներսում ընկած ցիկլը։ Քանի՞ անգամ է ցիկլը աշխատում indexOfMinimum-ի կանչի ժամանակ։ Այն կախված է լինում ենթազանգվածի չափից, որի վրայով պտտվում է։ Եթե ենթազանգվածն ամբողջ զանգվածն է (այս դեպքում՝ առաջին քայլը), ցիկլի մարմինն աշխատում է n անգամ։ Եթե ենթազանգվածի չափը 6 է, ցիկլի մարմինն աշխատում է 6 անգամ։
Օրինակ՝ ընդունիր, որ ամբողջական զանգվածի չափը 8 է, և մտածիր, թե ինչպես է ընտրական տեսակավորումն աշխատում։
  1. indexOfMinimum-ի առաջին կանչի ժամանակ այն նայում է զանգվածի յուրաքանչյուր արժեքին, և indexOfMinimum-ի ցիկլի մարմինն աշխատում է 8 անգամ։
  2. indexOfMinimum-ի երկրորդ կանչի ժամանակ այն նայում է 1-ից 7 ցուցիչներով ենթազանգվածի յուրաքանչյուր արժեքին, և indexOfMinimum-ի ցիկլի մարմինն աշխատում է 7 անգամ։
  3. Երրորդ կանչի ժամանակ այն նայում է 2-ից 7 ցուցիչներով ենթազանգվածին, ցիկլի մարմինն աշխատում է 6 անգամ։
  4. Չորրորդ կանչի ժամանակ այն նայում է 3-ից 7 ցուցիչներով ենթազանգվածին, ցիկլի մարմինն աշխատում է 5 անգամ։
  5. …
  6. indexOfMinimum-ի ութերորդ կանչի ժամանակ ցիկլի մարմինն աշխատում է միայն 1 անգամ։
Եթե հաշվենք, թե ընդհանուր քանի անգամ է indexOfMinimum-ի ցիկլի մարմինն աշխատում, ստանում ենք 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36։

Կողմնակի նշում: Հաշվել 1-ից n թվերի գումարը

Ինչպե՞ս արագ հաշվել 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 գումարը։ Այսպիսի հնարք արի կիրառենք։ Արի հետաքրքիր հերթականությամբ գումարենք թվերը։ Սկզբում գումարենք 8 + 1՝ ամենամեծ ու ամենափոքր թվերը։ Ստանում ենք 9։ Հետո գումարենք 7 + 2՝ երկրորդ ամենամեծ ու երկրորդ ամենափոքր թվերը։ Հետաքրքիր է․ նորից ստանում ենք 9։ Իսկ եթե 6 + 3-ը գումարե՞նք։ Նույնպես 9։ Վերջապես՝ 5 + 4։ Նորից 9։ Ուրեմն ի՞նչ ունենք։
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=4⋅9=36  \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ \end{aligned}
Կա չորս զույգ թիվ, որոնց բոլորի գումարները 9\ էր։ Հետևաբար, ահա ընդհանուր հնարք՝ հաջորդական ամբողջ թվերի գումարը հաշվելու համար․
  1. Գումարիր ամենամեծ ու ամենափոքր թիվը։
  2. Բազմապատկիր զույգերի քանակով։
Իսկ ի՞նչ կլինի, եթե հաջորդականության մեջ ամբողջ թվերի քանակը կենտ է, այսինքն՝ չենք կարող դրանք զույգավորել։ Դա կապ չունի։ Ուղղակի հաշվում ես մեջտեղում ընկած չզույգավորված թիվը՝ որպես կիսով չափ զույգ։ Օրինակ՝ արի գումարենք 1 + 2 + 3 + 4 + 5\ -ը։ Մենք ունենք երկու ամբողջական զույգ (1 + 5 ու 2 + 4, յուրաքանչյուրի գումարը՝ 6) և մեկ «կիսազույգ» (3, որը 6-ի կեսն է), ընդհանուր 2,5 զույգ։ Բազմապատկում ենք 2, comma, 5, dot, 6, equals, 15 և ստանում ենք ճիշտ պատասխանը:
Իսկ ի՞նչ կլինի, եթե հաջորդականությունը 1-ից n թվերն են։ Սա անվանում ենք թվաբանական պրոգրեսիա։ Ամենափոքր ու ամենամեծ թվերի գումարը n, plus, 1 է։ Քանի որ ընդհանուր կա n թիվ, կա n, slash, 2 զույգ (անկախ նրանից՝ n-ը կենտ է, թե զույգ)։ Հետևաբար, 1-ից n թվերի գումարը left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis է, որը հավասար է n, squared, slash, 2, plus, n, slash, 2։ Փորձիր այս բանաձևը n, equals, 5-ի և n, equals, 8-ի համար։

Ընտրական տեսակավորման ասիմպտոտային աշխատելու ժամանակի վերլուծություն

Ընտրական տեսակավորման ընդհանուր աշխատելու ժամանակն ունի երեք մաս․
  1. Բոլոր indexOfMinimum կանչերի աշխատելու ժամանակը։
  2. Բոլոր swap կանչերի աշխատելու ժամանակը։
  3. selectionSort ֆունկցիայի ցիկլի մնացած հատվածի աշխատելու ժամանակը։
2-րդ ու 3-րդ մասերը հեշտ են։ Մենք գիտենք, որ կա n կանչ swap-ի համար, և ամեն մի կանչի համար պահանջվում է հաստատուն ժամանակ։ Օգտագործելով ասիմպտոտային նշագրումը՝ swap-ի բոլոր կանչերի ժամանակը \Theta, left parenthesis, n, right parenthesis է։ selectionSort-ի ցիկլի մնացած հատվածն իրականում միայն ստուգում և մեծացնում է ցիկլի փոփոխականի արժեքը և կանչում indexOfMinimum ու swap ֆունկցիաները, հետևաբար այն ամեն n կրկնությունների ժամանակ աշխատում է հաստատուն ժամանակում՝ նույնպես \Theta, left parenthesis, n, right parenthesis ժամանակում։
1-ին մասում indexOfMinimum-ի բոլոր կանչերի աշխատելու ժամանակը հաշվելն արեցինք, ինչն ամենադժվար հատվածն էր։ indexOfMinimum-ում ցիկլի ամեն մի անհատական կրկնություն ծախսում է հաստատուն ժամանակ։ Այս ցիկլի կրկնությունների քանակը n է առաջին կանչին, հետո n, minus, 1, հետո n, minus, 2, և այսպես շարունակ։ Մենք արդեն տեսանք, որ այս գումարը՝ 1, plus, 2, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, plus, n թվաբանական պրոգրեսիա է, և այն հավասար է left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis կամ n, squared, slash, 2, plus, n, slash, 2։ Հետևաբար, indexOfMinimum-ի բոլոր կանչերի ընդհանուր ժամանակը կլինի ինչ-որ հաստատուն՝ բազմապատկած n, squared, slash, 2, plus, n, slash, 2։ big-Θ նշագրումն օգտագործելիս մեզ համար կարևոր չէ ոչ հաստատուն թիվը, ոչ 1/2-ը, ոչ էլ ցածր աստիճանի անդամը։ Հետևաբար, indexOfMinimum-ի բոլոր կանչերի ընդհանուր աշխատելու ժամանակը \Theta, left parenthesis, n, squared, right parenthesis է։
Գումարելով բոլոր մասերի աշխատելու ժամանակները՝ ստանում ենք \Theta, left parenthesis, n, squared, right parenthesis՝ indexOfMinimum-ի կանչերի համար, \Theta, left parenthesis, n, right parenthesis՝ swap-ի կանչերի համար և \Theta, left parenthesis, n, right parenthesis՝ selectionSort-ի ցիկլի մնացած մասի համար։ \Theta, left parenthesis, n, squared, right parenthesis անդամն ամենակարևորն է, և կարող ենք ասել, որ ընտրական տեսակավորման աշխատելու ժամանակը \Theta, left parenthesis, n, squared, right parenthesis է։
Ուշադրություն դարձրու, որ չկա որևէ դեպք, որի համար ընտրական տեսակավորումը շատ լավն է կամ շատ վատը։ indexOfMinimum-ի ցիկլը միշտ կկատարի n, squared, slash, 2, plus, n, slash, 2 կրկնություն՝ անկախ ներմուծված արժեքից։ Հետևաբար, կարող ենք ասել, որ ընտրական տեսակավորումը բոլոր դեպքերի համար աշխատում է \Theta, left parenthesis, n, squared, right parenthesis ժամանակում։
Տեսնենք, թե ինչպես \Theta, left parenthesis, n, squared, right parenthesis աշխատելու ժամանակը կազդի ընդհանուր աշխատելու ժամանակի վրա։ Ընդունենք, թե ընտրական տեսակավորումը մոտավորապես ծախսում է n, squared, slash, 10, start superscript, 6, end superscript վայրկյան՝ n արժեք տեսակավորելու համար։ Արի սկսենք n-ի փոքր արժեքից, վերցնենք n, equals, 100։ Հետևաբար, ընտրական տեսակավորման աշխատելու ժամանակը մոտ 100, squared, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 վայրկյան է։ Լավ արագ է։ Իսկ ի՞նչ կլինի, եթե n, equals, 1000։ Հետևաբար, ընտրական տեսակավորման աշխատելու ժամանակը մոտ 1000, squared, slash, 10, start superscript, 6, end superscript, equals, 1 վայրկյան է։ Զանգվածը մեծացավ 10 անգամ, բայց աշխատելու ժամանակը մեծացավ 100 անգամ։ Իսկ եթե n, equals, 1000000։ Հետևաբար, ընտրական տեսակավորման աշխատելու ժամանակը մոտ 1000000, squared, slash, 10, start superscript, 6, end superscript, equals, 1000000 վայրկյան է, որը 11,5 օրից շատ է։ Զանգվածը մեծացավ 1000 անգամ, բայց աշխատելու ժամանակը մեծացավ միլիոն անգամ։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

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

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