Big-O նշագրում

Մենք օգտագործում ենք big-Θ նշագրումը, որ ասիմպտոտային կերպով հաստատուն թվերով սահմանափակենք աշխատելու ժամանակի աճը։ Երբեմն մեզ պետք կգա սահմանափակել միայն վերևից։

Օրինակ՝ չնայած, որ երկուական որոնման վատագույն աշխատելու ժամանակը $\mathrm{\Theta }({\log }_{2}n)$‍ է, սխալ կլինի ասել, որ երկուական որոնումն աշխատում է $\mathrm{\Theta }({\log }_{2}n)$‍ ժամանակում բոլոր դեպքերում։ Իսկ ի՞նչ կլինի, եթե գտնենք պետք եկած արժեքն առաջին գուշակումից։ Ուրեմն այն աշխատեց $\mathrm{\Theta }(1)$‍ ժամանակում։ Երկուական որոնման աշխատելու ժամանակը երբեք $\mathrm{\Theta }({\log }_{2}n)$‍-ից վատ չէ, բայց հաճախ դրանից լավ է։

Ճիշտ կլինի կազմել ասիմպտոտային նշագրում, որը ցույց կտա, որ «աշխատելու ժամանակն աճում է այսքան, բայց այն ավելի դանդաղ էլ կարող է աճել»։ Այս դեպքերի համար օգտագործում ենք big-O նշագրումը։

Եթե աշխատելու ժամանակը $O(f(n))$‍ է, ապա բավականաչափ մեծ $n$‍-ի համար աշխատելու ժամանակն առավելագույնս $k\cdot f(n)$‍ է ինչ-որ հաստատուն $k$‍-ի համար։ Ահա թե ինչպես կարող ենք հասկանալ $O(f(n))$‍-ի աշխատելու ժամանակը․

Մենք ասում ենք, որ աշխատելու ժամանակը «$f(n)$‍ ֆունկցիայի big-O» է կամ ուղղակի «$f(n)$‍-ի O»։ Մենք օգտագործում ենք big-O նշագրումը ասիմպտոտոյին վերին սահմանների համար, քանի որ այն վերևից սահմանափակում է աշխատելու ժամանակի աճը մուտքագրված արժեքների բոլոր չափերի համար։

Հիմա մենք բոլոր դեպքերի համար կարող ենք ցույց տալ երկուական որոնման աշխատելու ժամանակը։ Կարող ենք ասել, որ երկուական որոնման աշխատելու ժամանակը միշտ $O({\log }_{2}n)$‍ է։ Կարող ենք ավելի լավ սահմանում տալ վատագույն աշխատելու ժամանակի համար՝ $\mathrm{\Theta }({\log }_{2}n)$‍։ Բայց ապահով պնդումը կլինի այն, որը ճիշտ կլինի բոլոր դեպքերի համար, և այս դեպքում մենք կարող ենք ասել, որ երկուական որոնումն աշխատում է $O({\log }_{2}n)$‍ ժամանակում։

Եթե վերադառնանք big-Θ նշագրման սահմանմանը, կարող ես նկատել, որ այն շատ նման է big-O նշագրմանը, միայն թե big-Θ նշագրումը սահմանափակում է աշխատելու ժամանակը ներքևից ու վերևից, ոչ թե միայն վերևից։ Եթե ասենք, որ աշխատելու ժամանակը $\mathrm{\Theta }(f(n))$‍ է ինչ-որ կոնկրետ դեպքում, ապա այն նաև $O(f(n))$‍ է։ Օրինակ՝ կարող ենք ասե՝ քանի որ երկուական որոնման վատագույն աշխատելու ժամանակը $\mathrm{\Theta }({\log }_{2}n)$‍ է, այն նաև $O({\log }_{2}n)$‍ է։

Հակառակը ոչ միշտ է ճիշտ․ ինչպես տեսել ենք, կարող ենք ասել, որ երկուական որոնումը միշտ աշխատում է $O({\log }_{2}n)$‍ ժամանակում, բայց ոչ միշտ է աշխատում $\mathrm{\Theta }({\log }_{2}n)$‍ ժամանակում։

Քանի որ big-O նշագրումը տալիս է միայն ասիմպտոտային վերին սահման, այլ ոչ թե ասիմպտոտային մոտ սահման, մենք կարող ենք ասել պնդումներ, որոնք առաջին հայացքից սխալ են թվում, բայց տեխնիկապես ճիշտ են։ Օրինակ՝ լրիվ ճիշտ կլինի, եթե ասենք, որ երկուական որոնումն աշխատում է $O(n)$‍ ժամանակում, քանի որ աշխատելու ժամանակն աճում է ոչ ավել, քան $n$‍ արագությամբ, նույնիսկ ավելի դանդաղ։

Այսպես մտածիր։ Պատկերացրու՝ գրպանումդ ունես 10 դոլար։ Գնում ես ընկերոջդ մոտ և ասում ես․ «Իմ գրպանում գումար կա, և վստահեցնում եմ, որ այն մեկ միլիոն դոլարից քիչ է»։ Քո պնդումը ճիշտ է, բայց ոչ այնքան հստակ։

Մեկ միլիոն դոլարը 10 դոլարի վերին սահման է այնպես, ինչպես $O(n)$‍-ն է երկուական որոնման վերին սահման։ Մեկ այլ՝ ոչ հստակ վերին սահման երկուական որոնման համար $O(n^2)$‍-ն է, կամ $O(n^3)$‍-ը, կամ էլ $O(2^n)$‍-ը։ Բայց երկուական որոնման աշխատելու ժամանակը $\mathrm{\Theta }(n)$‍-ով, $\mathrm{\Theta }(n^2)$‍-ով, $\mathrm{\Theta }(n^3)$‍-ով կամ $\mathrm{\Theta }(2^n)$‍-ով նկարագրելը սխալ կլինի։

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