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

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

Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 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, start subscript, 1, end subscript, dot, n է, որտեղ c, start subscript, 1, end subscript-ը մեկ ցիկլի հաշվարկման գումարային ժամանակն է։ Այս պահին չենք կարող ասել c, start subscript, 1, end subscript-ի արժեքը, որովհետև այն կախված է համակարգչի արագությունից, օգտագործվող ծրագրավորման լեզվից, կոմպիլյատորից կամ մեկնաբանիչից (interpreter), որով սկզբնական ծրագիրը թարգմանվում է աշխատող կոդի և շատ այլ հանգամանքներից:

Այս կոդում for-loop-ն աշխատացնելու և վերջում հնարավոր -1 վերադարձնելու համար մի փոքր հավելյալ ժամանակ է ծախսում (ներառյալ guess-ին 0 վերագրելը)։ Արի այս հավելյալ ժամանակը նշանակենք c, start subscript, 2, end subscript-ով, որը նույնպես հաստատուն է։ Հետևաբար, գծային որոնումով վատագույն դեպքի ընդհանուր ժամանակը հավասար է c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript։

Ինչպես պնդեցինք, հաստատուն գործակից c, start subscript, 1, end subscript-ն ու ցածր կարգի անդամ c, start subscript, 2, end subscript-ը բավական չեն գնահատելու աշխատելու աճման արագությունը։ Հատկանշականը այն է, որ գծային որոնման աճման արագությունը վատագույն դեպքում նման է n զանգվածի չափին։ \Theta, left parenthesis, n, right parenthesis-ով նշագրվում է նմանատիպ ծրագրերի աշխատացնելու ժամանակը ։ Դա հունարենի այբուբենում թետա տառն է, և մենք ասում ենք «big-Theta of n» («n-ի մեծ թետա») կամ ուղղակի «Theta of n» («n-ի թետա»)։

Երբ ասում ենք, որ աշխատելու ժամանակը \Theta, left parenthesis, n, right parenthesis է, նկատի ունենք, որ երբ n-ը դառնում է բավականին մեծ, աշխատելու ժամանակը առնվազն k, start subscript, 1, end subscript, dot, n է և առավելագույնը k, start subscript, 2, end subscript, dot, n կամայական k, start subscript, 1, end subscript և k, start subscript, 2, end subscript հաստատունների համար։ Ահա թե ինչպես հասկանալ \Theta, left parenthesis, n, right parenthesis-ը․

n-ի փոքր արժեքների դեպքում մեզ համար տարբերություն չկա, թե ինչպես է աշխատելու ժամանակը համեմատվում k, start subscript, 1, end subscript, dot, n-ի կամ k, start subscript, 2, end subscript, dot, n-ի հետ։ Բայց երբ n-ի արժեքը բավականաչափ մեծանում է, աշխատելու ժամանակը պետք է ընկած լինի k, start subscript, 1, end subscript, dot, n-ի ու k, start subscript, 2, end subscript, dot, n-ի միջև։ Քանի դեռ k, start subscript, 1, end subscript-ն ու k, start subscript, 2, end subscript-ը գոյություն ունեն, մենք ասում ենք, որ աշխատելու ժամանակը \Theta, left parenthesis, n, right parenthesis է։

big-Θ նշագրելիս միայն n-ով չենք սահմանափակվում։ Կարող ենք օգտագործել ցանկացած ֆունկցիա, ինչպիսիք են n, squared, n, log, start base, 2, end base, n ֆունկցիաները կամ n-ով մեկ այլ ֆունկցիա։ Ահա թե ինչպես կարող ենք պատկերացնել աշխատելու ժամանակի մասին, օրինակ՝ \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis-ն որևէ f, left parenthesis, n, right parenthesis ֆունկցիայի համար․

Երբ n-ի արժեքը բավականաչափ մեծ է դառնում, աշխատելու ժամանակն ընկնում է k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis-ի ու k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis-ի միջև։

Գործնականում հաստատուն գործակիցներն ու ցածր աստիճանով անդամները կարող ենք անտեսել։ big-Θ նշագրումն օգտագործելու մեկ այլ առավելությունն այն է, որ հարկավոր չէ անհանգստանալ, թե ինչ չափման միավորներ ենք օգտագործում։ Ենթադրենք, գտնում ենք, որ աշխատելու ժամանակը 6, n, squared, plus, 100, n, plus, 300 միկրովայրկյան է։ Կամ գուցե այն միլիվայրկյան է։ Big-Θ-ը օգտագործելիս կարող ես չնշել։ Դու նաև ազատվում ես 6 գործակցից և ցածր աստիճանով անդամներից՝ 100, n, plus, 300, և նշում ես, որ աշխատելու ժամանակը \Theta, left parenthesis, n, squared, right parenthesis է։

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

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

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

Մուտք գործել

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

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

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