Երկուական որոնման աշխատելու ժամանակը

Մենք գիտենք, որ $n$n տարրերով զանգվածի վրա գծային որոնումը կարող է թիվը գտնել ընդհուպ մինչև $n$n որոնում հետո։ Դու երևի արդեն հասկացել ես, որ երկուական որոնումը գծային որոնման համեմատ ավելի քիչ կռահում է կատարում։ Երևի նաև հասկացել ես, որ որքան զանգվածի տարրերի քանակը շատանում է, այդքան ավելի անկնհայտ է դառնում երկուական որոնման առավելությունը գծային որոնման համեմատ։ Արի միասին վերլուծենք երկուական որոնման կռահումների առավելագույն քանակը։

Միտքն այն է, որ երբ երկուական որոնումը կատարում է սխալ կռահում, զանգվածի հնարավոր ճիշտ պատասխանների քանակը կրճատվում է ներկայի քանակի առնվազն կեսով։ Եթե հնարավոր արժեքների քանակը 32-ն է, ապա սխալ կռահելուց հետո հնարավոր արժեքների քանակը կդառնա 16։ Երկուական որոնումը կիսում է հնարավոր արժեքների քանակը ամեն սխալ կռահումից հետո։

Եթե սկսենք 8 երկարությամբ զանգվածից, ուրեմն սխալ կռահումները կիսում են հնարավոր արժեքների քանակը 4-ի, հետո՝ 2-ի, իսկ հետո՝ 1-ի։ Երբ հնարավոր արժեքների քանակը դառնում է միայն մեկ տարր, այլևս գուշակություններ չեն լինում։ 1 տարրը կռահելիս ստանում ենք ճիշտ կամ սխալ, և խնդիրը վերջանում է։ Հետևաբար, 8 երկարությամբ զանգվածում մեր ուզած տեղեկությունը կամ տարրը երկուական որոնմամբ կգտնենք առավելագույնս չորս քայլից։

Ի՞նչ ես կարծում՝ ի՞նչ կլինի 16 տարրանոց զանգվածի հետ։ Եթե կարծում ես, որ առաջին քայլից հետո դուրս կմնա 8 հնարավոր տարբերակ, իսկ 8-ը կմնան, ուրեմն ճիշտ ես հասկացել։ Հետևաբար, 16 տարրի դեպքում մեզ հարկավոր կլինի առավելագույնը հինգ քայլ։

Դու արդեն երևի սկսում ես գտնել կապը։ Ամեն անգամ, երբ մենք զանգվածի չափսերը կրկնապատկում ենք, մեր առավելագույն քայլերի քանակը մեկով ավելանում է։ Հիմա պատկերացնենք, թե մեզ պետք է առավելագույնը $m$m քայլ $n$n երկարությամբ զանգվածի համար։ Հետևաբար, $2n$2, n երկարությամբ զանգվածի համար առաջին կռահումից հնարավոր տարբերակները ուղիղ կեսով կպակասեն՝ դարձնելով այն $n$n, որից հետո էլ մենք գիտենք, որ առավելագույն քայլերի քանակը $m$m-ն է։ Հետևաբար, մեր քայլերի քանակն այս դեպքում $m+1$m, plus, 1 է։

Արի վերցնենք $n$n երկարությամբ զանգվածը։ Վատագույն դեպքում մենք կարող ենք արտահայտել կռահումների քանակը այսպես, «քանի անգամ կարող ենք շարունակաբար կիսել, $n$n-ից սկսելով, մինչև ստանանք 1, գումարած մեկ»։ Բայց այսպես անհարմար է գրի առնել։

Բարեբախտաբար գոյություն ունի մաթեմատիկական ֆունկցիա, որը հաշվում է $n$n թվից սկսած շարունակական կիսումների քանակը, մինչև կստանանք 1։ Դա 2 հիմքով $n$n-ի լոգարիթմն է։ Դա շատ հաճախ գրվում է որպես $\log_2 n$log, start base, 2, end base, n, բայց հնարավոր է համակարգչային գիտությունների տեքստերում հանդիպես նաև այս տարբերակին՝ $\lg n$\lg, n։ (Ուզում ես լոգարիթմերի մասին իմանալ ավելի՞ն։ Սեղմիր այստեղ։)

Այս աղյուսակը ցույց է տալիս 2 հիմքով լոգարիթմի արժեքները $n$n-ի տարբեր արժեքների դեպքում։

Նույն աղյուսակը կարող ենք նայել գրաֆիկով․

n-ի ավելի փոքր արժեքների գրաֆիկը․

Լոգարիթմի ֆունկցիան դանդաղ է աճում։ Լոգարիթմերը ցուցիչների շրջված տարբերակներն են։ Ցուցիչները, ընդհակառակը, աճում են շատ արագ։ Եթե $\log_2 n = x$log, start base, 2, end base, n, equals, x, ապա $n = 2^x$n, equals, 2, start superscript, x, end superscript։ Օրինակ, եթե $\log_2 128 = 7$log, start base, 2, end base, 128, equals, 7, ուրեմն $2^7 = 128$2, start superscript, 7, end superscript, equals, 128։

Դա երկուական որոնման աշխատաժամանակը հաշվելու գործընթացը հեշտացնում է այն $n$n-երի համար, որոնք 2-ի աստիճան են։ Եթե $n$n-ը 128 է, երկուական որոնման աշխատաժամանակը կլինի առավելագույնը 8 ($\log_2 128 + 1$log, start base, 2, end base, 128, plus, 1) քայլ։

Իսկ ի՞նչ, եթե $n$n-ը 2-ի աստիճան չէ։ Այս դեպքում մենք փնտրում ենք դրանից փոքր, ամենամոտ 2-ի աստիճան թիվը։ 1000 երկարություն ունեցող զանգվածի համար ամենամոտ 2-ի աստիճանը 512-ն է, որը $2^{9}$2, start superscript, 9, end superscript-ն է։ Հետևաբար, կարող ենք $\log_2 1000$log, start base, 2, end base, 1000-ը մոտարկել 9-ից մեծ և 10-ից փոքր թիվ կամ օգտագործել հաշվիչ և տեսնել, որ այն հավասար է 9,97։ Դրան մեկ գումարելիս էլ ստանում ենք 10,97։ Տասնորդական թվի դեպքում կլորացնում ենք դեպի ամենամոտ ամբողջ թիվը։ Հետևաբար, 1000 տարր ունեցող զանգվածում երկուական որոնումով առավելագույնը 10 քայլից կգտնենք ցանկալի թիվը։

Թայքո-2 աստղերի տեղեկագրքի դեպքում, որտեղ կա 2,539,913 աստղ, 2-ի ամենամոտ աստիճանը $2^{21}$2, start superscript, 21, end superscript-ն է (որը հավասար է 2,097,152), հետևաբար մեզ առավելագույնը պետք կգա 22 քայլ։ Միանշանակ ավելի լավ ու արդյունավետ է, քան գծային որոնումը։

$n$n և $\log _{2} n$log, start base, 2, end base, n ֆունկցիաների գրաֆիկների համեմատություն․

Հաջորդ հոդվածում կտեսնենք, թե ինչպես են համակարգչային գիտակները նշագրում գծային որոնման և երկուական որոնման աշխատելու ժամանակները՝ օգտագործելով նշագրում, որը ցույց է տալիս աշխատելու ժամանակի ամենակարևոր հատվածը և անտեսում ոչ կարևորները։

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