Big-Ω (Big-Omega) նշագրում

Երբեմն պետք է ասենք, որ ալգորիթմն աշխատում է առնվազն ինչ-որ ժամանակում՝ առանց վերին սահման նշելու։ Այս դեպքում օգտագործում ենք big-Ω նշագրումը՝ հունարեն այբուբենի օմեգա տառը։

Եթե աշխատելու ժամանակը $\Omega(f(n))$\Omega, 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-ով։ Ահա թե ինչպես պետք է պատկերացնել $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis աշխատելու ժամանակը․

Մենք ասում ենք, որ աշխատելու ժամանակը «$f(n)$f, left parenthesis, n, right parenthesis ֆունկցիայի big-Ω» է։ Մենք օգտագործում ենք 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-ը, դրանից նաև բախում է $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis-ը։ Հետևաբար, կարող ենք ասել, որ երկուական որոնման վատագույն աշխատելու ժամանակը $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis է։

big-Ω նշագրումն օգտագործելով նաև կարող ենք ասել ոչ հստակ, բայց ճշգրիտ պնդումներ։ Օրինակ, եթե գրպանումդ կա միլիոն դոլար, դու կարող ես հանգիստ ասել՝ «Իմ գրպանում կա գումար, և դա առնվազն 10 դոլար է»։ Դա ճիշտ է, բայց ոչ այնքան հստակ։ Նմանապես, մենք կարող ենք ճշգրտորեն, բայց ոչ հստակ ասել, որ երկուական որոնման վատագույն աշխատելու ժամանակը $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis է, որովհետև գիտենք, որ այն առնվազն հաստատուն ժամանակ է։

Իհարկե, երբ խոսում ենք ալգորիթմներից, պետք է փորձենք դրանց աշխատելու ժամանակը բնութագրել որքան հնարավոր է հստակ։ Մենք ցույց ենք տալիս ոչ հստակ պնդումների օրինակներ, որ ավելի լավ հասկանաս big-$\Omega$\Omega, big-$O$O և big-$\Theta$\Theta նշագրումները։

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