Big-O նշագրում

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

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

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

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

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

Հիմա մենք բոլոր դեպքերի համար կարող ենք ցույց տալ երկուական որոնման աշխատելու ժամանակը։ Կարող ենք ասել, որ երկուական որոնման աշխատելու ժամանակը միշտ $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis է։ Կարող ենք ավելի լավ սահմանում տալ վատագույն աշխատելու ժամանակի համար՝ $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis։ Բայց ապահով պնդումը կլինի այն, որը ճիշտ կլինի բոլոր դեպքերի համար, և այս դեպքում մենք կարող ենք ասել, որ երկուական որոնումն աշխատում է $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis ժամանակում։

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

Հակառակը ոչ միշտ է ճիշտ․ ինչպես տեսել ենք, կարող ենք ասել, որ երկուական որոնումը միշտ աշխատում է $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis ժամանակում, բայց ոչ միշտ է աշխատում $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis ժամանակում։

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

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

Մեկ միլիոն դոլարը 10 դոլարի վերին սահման է այնպես, ինչպես $O(n)$O, left parenthesis, n, right parenthesis-ն է երկուական որոնման վերին սահման։ Մեկ այլ՝ ոչ հստակ վերին սահման երկուական որոնման համար $O(n^2)$O, left parenthesis, n, squared, right parenthesis-ն է, կամ $O(n^3)$O, left parenthesis, n, cubed, right parenthesis-ը, կամ էլ $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis-ը։ Բայց երկուական որոնման աշխատելու ժամանակը $\Theta(n)$\Theta, left parenthesis, n, right parenthesis-ով, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis-ով, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis-ով կամ $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis-ով նկարագրելը սխալ կլինի։

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