If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

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

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

Երբեմն պետք է ասենք, որ ալգորիթմն աշխատում է առնվազն ինչ-որ ժամանակում՝ առանց վերին սահման նշելու։ Այս դեպքում օգտագործում ենք big-Ω նշագրումը՝ հունարեն այբուբենի օմեգա տառը։
Եթե աշխատելու ժամանակը \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis է, հետևաբար մեծ n-երի համար աշխատելու ժամանակը k, dot, f, left parenthesis, n, right parenthesis է՝ ինչ-որ հաստատուն k-ով։ Ահա թե ինչպես պետք է պատկերացնել \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis աշխատելու ժամանակը․
Մենք ասում ենք, որ աշխատելու ժամանակը «f, left parenthesis, n, right parenthesis ֆունկցիայի big-Ω» է։ Մենք օգտագործում ենք big-Ω նշագրումը ասիմպտոտային ստորին սահմանների համար, քանի որ այն ներքևից սահմանափակում է աշխատելու ժամանակի աճը մուտքագրված արժեքների բոլոր չափերի համար։
Այնպես, ինչպես \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis-ից բխում է O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis-ը, դրանից նաև բախում է \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis-ը։ Հետևաբար, կարող ենք ասել, որ երկուական որոնման վատագույն աշխատելու ժամանակը \Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis է։
big-Ω նշագրումն օգտագործելով նաև կարող ենք ասել ոչ հստակ, բայց ճշգրիտ պնդումներ։ Օրինակ, եթե գրպանումդ կա միլիոն դոլար, դու կարող ես հանգիստ ասել՝ «Իմ գրպանում կա գումար, և դա առնվազն 10 դոլար է»։ Դա ճիշտ է, բայց ոչ այնքան հստակ։ Նմանապես, մենք կարող ենք ճշգրտորեն, բայց ոչ հստակ ասել, որ երկուական որոնման վատագույն աշխատելու ժամանակը \Omega, left parenthesis, 1, right parenthesis է, որովհետև գիտենք, որ այն առնվազն հաստատուն ժամանակ է։
Իհարկե, երբ խոսում ենք ալգորիթմներից, պետք է փորձենք դրանց աշխատելու ժամանակը բնութագրել որքան հնարավոր է հստակ։ Մենք ցույց ենք տալիս ոչ հստակ պնդումների օրինակներ, որ ավելի լավ հասկանաս big-\Omega, big-O և big-\Theta նշագրումները։

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

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

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