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

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

Դաս 3: Ասիմպտոտային նշագրում

Big-θ (Big-Theta) նշագրում

Արի նայենք գծային որոնման կոդին․

var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // գտնվել է
    }
  }
  return -1;  // չի գտնվել
};

Արի զանգվածի չափը (array.length) նշանակենք

n

-ով։ for ցիկլի աշխատելու առավելագույն քանակը

n

անգամ է, և այդ ընթացքում վատագույն դեպքում կարող է փնտրել տարրը և չգտնել այն:

for ցիկլի ամեն մի կրկնության ժամանակ այն պետք է կատարի մի քանի գործողություն.

guess-ը համեմատի array.length-ի հետ,
array[guess]-ը համեմատի targetValue-ի հետ,
վերադարձնի guess-ի արժեքը,
guess-ը մեկով մեծացնի։

Այս յուրաքանչյուր փոքր հաշվարկը կատարելիս ծախսվում է հաստատուն քանակով ժամանակ։ Եթե for ցիկլն աշխատում է

n

անգամ, ապա

n

կրկնությունների ժամանակը

c_{1} \cdot n

է, որտեղ

c_{1}

-ը մեկ ցիկլի հաշվարկման գումարային ժամանակն է։ Այս պահին չենք կարող ասել

c_{1}

-ի արժեքը, որովհետև այն կախված է համակարգչի արագությունից, օգտագործվող ծրագրավորման լեզվից, կոմպիլյատորից կամ մեկնաբանիչից (interpreter), որով սկզբնական ծրագիրը թարգմանվում է աշխատող կոդի և շատ այլ հանգամանքներից:

Այս կոդում for-loop-ն աշխատացնելու և վերջում հնարավոր -1 վերադարձնելու համար մի փոքր հավելյալ ժամանակ է ծախսում (ներառյալ guess-ին 0 վերագրելը)։ Արի այս հավելյալ ժամանակը նշանակենք

c_{2}

-ով, որը նույնպես հաստատուն է։ Հետևաբար, գծային որոնումով վատագույն դեպքի ընդհանուր ժամանակը հավասար է

c_{1} \cdot n + c_{2}

Ինչպես պնդեցինք, հաստատուն գործակից

c_{1}

-ն ու ցածր կարգի անդամ

c_{2}

-ը բավական չեն գնահատելու աշխատելու աճման արագությունը։ Հատկանշականը այն է, որ գծային որոնման աճման արագությունը վատագույն դեպքում նման է

n

զանգվածի չափին։

Θ (n)

-ով նշագրվում է նմանատիպ ծրագրերի աշխատացնելու ժամանակը ։ Դա հունարենի այբուբենում թետա տառն է, և մենք ասում ենք «big-Theta of n» («

n

-ի մեծ թետա») կամ ուղղակի «Theta of n» («

n

-ի թետա»)։

Երբ ասում ենք, որ աշխատելու ժամանակը

Θ (n)

է, նկատի ունենք, որ երբ

n

-ը դառնում է բավականին մեծ, աշխատելու ժամանակը առնվազն

k_{1} \cdot n

է և առավելագույնը

k_{2} \cdot n

կամայական

k_{1}

k_{2}

հաստատունների համար։ Ահա թե ինչպես հասկանալ

Θ (n)

-ը․

n

-ի փոքր արժեքների դեպքում մեզ համար տարբերություն չկա, թե ինչպես է աշխատելու ժամանակը համեմատվում

k_{1} \cdot n

-ի կամ

k_{2} \cdot n

-ի հետ։ Բայց երբ

n

-ի արժեքը բավականաչափ մեծանում է, աշխատելու ժամանակը պետք է ընկած լինի

k_{1} \cdot n

-ի ու

k_{2} \cdot n

-ի միջև։ Քանի դեռ

k_{1}

-ն ու

k_{2}

-ը գոյություն ունեն, մենք ասում ենք, որ աշխատելու ժամանակը

Θ (n)

է։

big-Θ նշագրելիս միայն

n

-ով չենք սահմանափակվում։ Կարող ենք օգտագործել ցանկացած ֆունկցիա, ինչպիսիք են

n^{2}

n \log_{2} n

ֆունկցիաները կամ

n

-ով մեկ այլ ֆունկցիա։ Ահա թե ինչպես կարող ենք պատկերացնել աշխատելու ժամանակի մասին, օրինակ՝

Θ (f (n))

-ն որևէ

f (n)

ֆունկցիայի համար․

Երբ

n

-ի արժեքը բավականաչափ մեծ է դառնում, աշխատելու ժամանակն ընկնում է

k_{1} \cdot f (n)

-ի ու

k_{2} \cdot f (n)

-ի միջև։

Գործնականում հաստատուն գործակիցներն ու ցածր աստիճանով անդամները կարող ենք անտեսել։ big-Θ նշագրումն օգտագործելու մեկ այլ առավելությունն այն է, որ հարկավոր չէ անհանգստանալ, թե ինչ չափման միավորներ ենք օգտագործում։ Ենթադրենք, գտնում ենք, որ աշխատելու ժամանակը

6 n^{2} + 100 n + 300

միկրովայրկյան է։ Կամ գուցե այն միլիվայրկյան է։ Big-Θ-ը օգտագործելիս կարող ես չնշել։ Դու նաև ազատվում ես 6 գործակցից և ցածր աստիճանով անդամներից՝

100 n + 300

, և նշում ես, որ աշխատելու ժամանակը

Θ (n^{2})

է։

big-Θ նշագրումն օգտագործելիս նշում ենք, որ աշխատելու ժամանակն ունի ասիմպտոտիկ նեղ սահման։ Ասիմտոտիկ, որովհետև այն գործում է միայն

n

-ի մեծ արժեքների համար։ Նեղ սահման, որովհետև աշխատելու ժամանակը վերևից և ներքևից սահմանափակել ենք հաստատուն գործակցով։

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

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

Մուտք գործել

Դասակարգել ըստ

Առայժմ հրապարակումներ չկան։

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