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

Առայժմ մենք վերլուծել ենք գծային որոնումն ու երկուական որոնումը՝ հաշվելով դրանց առավելագույն քայլերի քանակը։ Սակայն մենք ուզում ենք նաև իմանալ, թե որքան ժամանակ են այդ ալգորիթմները ծախսում։ Մեզ հետաքրքրում է ժամանակը, ոչ թե քայլերի քանակը։ Գծային որոնման ու երկուական որոնման աշխատաժամանակները ներառում են գուշակություններ կատարելու ժամանակը և ոչ միայն։

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

Արի մի փոքր խոսենք ալգորիթմի աշխատելու ժամանակի մասին, որի համար երկու հասկացություն կկապակցենք իրար։ Առաջինը, թե որքան ժամանակում է ալգորիթմն աշխատում՝ կախված մուտքագրված արժեքի մեծությունից։ Մենք արդեն տեսանք, որ առավելագույն քայլերի քանակը գծային որոնման և երկուական որոնման մեջ աճում է զանգվածի երկարության մեծանալու հետ։ Կամ վերցնենք GPS-ի օրինակը։ Եթե համակարգն իմանա ճանապարհներ գծելու ալգորիթմը, ոչ թե մեկ առ մեկ ճանաչի բոլոր փողոցներն ու նրբանցքները, այն ավելի արագ կաշխատի, այնպես չէ՞։ Հետևաբար, մենք պետք է ալգորիթմի աշխատելու ժամանակը հասկանանք որպես ֆունկցիա՝ կախված մուտքագրված չափից։

Երկրորդ միտքն այն է, որ պետք է փորձենք հասկանալ, թե մուտքագրված արժեքի աճի հետ ինչ արագությամբ է աճում ֆունկցիան։ Սա կոչվում է աշխատելու ժամանակի աճման արագություն։ Այն կառավարելի դարձնելու համար պետք է ուշադրություն դարձնենք ամենակարևոր մասերի վրա, և անկարևոր մասերի մասին մի պահ մոռանանք։ Օրինակ՝ պատկերացրու ալգորիթմ, որն աշխատում է $n$‍ մուտքագրված չափով և գտնում է $6n^2+100n+300$‍-ի արժեքը։ $6n^2$‍ կտորը $100n+300$‍-ից ավելի մեծ է դառնում, երբ $n$‍-ը հասնում է որոշակի արժեքի, այս դեպքում՝ 20-ի։ Այս գրաֆիկը ցույց է տալիս $6n^2$‍-ի ու $100n+300$‍-ի արժեքները 0-ից 100 ունեցող $n$‍-երի համար․

Կարող ենք ասել, որ այս ալգորիթմի աշխատելու ժամանակն աճում է $n^2$‍-ի հետ՝ դեն նետելով 6 գործակիցն ու $100n+300$‍ արտահայտությունը։ Էական չէ, թե ինչ է գործակիցը․ երբ մեր ալգորիթմի աշխատելու ժամանակը $a{n}^2+bn+c$‍ տեսքի է $a>0$‍, $b$‍ և $c$‍ թվերի դեպքում, միշտ կլինի $n$‍-ի արժեք, որը տեղադրելիս կստանանք, որ $a{n}^2$‍-ը մեծ է $bn+c$‍-ից, և $n$‍-ի աճելու հետ կաճի դրանց տարբերությունը։ Ահա մի գրաֆիկի օրինակ, որ ցույց է տալիս $0,6n^2$‍ և $1000n+3000$‍ գրաֆիկները, և չնայած մենք $n^2$‍-ի գործակիցը բաժանել ենք 10-ի, իսկ մյուս գործակիցն ու ազատ անդամը բազմապատկել 10-ով, կորն ինչ-որ պահից սկսում է գերազանցել ուղղին․

$n$‍-ի արժեքը, երբ $0,6n^2$‍-ն մեծ է դառնում $1000n+3000$‍-ից, մեծանում է, բայց միշտ կլինի այդ հատման կետը, անկախ հաստատունի արժեքից։

Մի կողմ թողնելով անկարևոր անդամներն ու հաստատուն գործակիցները՝ մենք կարող ենք կենտրոնանալ ալգորիթմի աշխատելու ժամանակի և դրա աճման արագության վրա՝ առանց շեղվելու այն մասերի վրա, որոնք մեզ միայն կխանգարեն։ Երբ հանում ենք հաստատուն գործակիցները և անկարևոր անդամները, կմնա միայն ասիմպտոտային նշագրումը։ Ասիմպտոտային նշագրումը կարող ենք ներկայացնել երեք տեսքով՝ big-$\mathrm{\Theta }$‍ նշագրում, big-O նշագրում և big-$\mathrm{\Omega }$‍ նշագրումը։

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