Big-O նշումը նշում է, որն օգտագործվում է ֆունկցիաների երկարաժամկետ աճի տեմպերի մասին խոսելու համար: Այն հաճախ օգտագործվում է ալգորիթմների վերլուծության համար, խոսելու ալգորիթմի կատարման կամ հարակից հասկացությունների մասին, ինչպիսիք են տարածության բարդությունը:
O(1) — Մշտական կատարման ժամանակ.
Ալգորիթմը O(1) բարդության է, եթե այն պահանջում է մշտական կատարման ժամանակ: Կատարման ժամանակը նույնն է՝ անկախ մուտքային արժեքների չափից։ Ով ասում է, որ կայունություն նույնպես ասում է O(1):
O(log n) — Լոգարիթմական կատարման ժամանակ.
Պարզապես լոգարիթմական միտումը էքսպոնենցիալ միտումի հակառակն է: Այնտեղ, որտեղ էքսպոնենցիալ միտումը ժամանակի ընթացքում կբազմապատկվի, լոգարիթմական միտումը կբաժանվի:
O(n) — Գծային կատարման ժամանակ`
Ալգորիթմի մասին ասում ենք, որ այն ունի O(n) բարդություն, եթե դրա կատարման ընթացքում նրանից պահանջվում է անցնել յուրաքանչյուր մուտքային տարր:
O(n log (n)) գծային բարդություն՝
օգտագործում է նույն մոտեցումը, ինչ լոգարիթմական բարդությունը, բացառությամբ, որ դա անում է n մուտքագրման յուրաքանչյուր տարրի վրա:
O(n²) — Քառակուսի/քառակուսի կատարման ժամանակ՝
Ալգորիթմը, որի կատարման ժամանակը ուղիղ համեմատական է մուտքային տվյալների հավաքածուի չափի քառակուսուն, կոչվում է O(n²) բարդության:
O(k^n) — Էքսպոնենցիալ կատարման ժամանակ.
Ալգորիթմը, որի կատարման ժամանակը երկրաչափականորեն աճում է, աճում է k անգամ n-ի յուրաքանչյուր աճի համար:
Ակնհայտ է, որ որքան կարճ է կատարման ժամանակը, այնքան ավելի արդյունավետ է ալգորիթմը:
Բացի այդ, մենք օգտագործում ենք այս նշումը տարածության բարդության համար՝ որոշելու լրացուցիչ հիշողության անհրաժեշտությունը:
Ենթադրենք, ալգորիթմը չի պահանջում լրացուցիչ կամ ֆիքսված քանակի լրացուցիչ հիշողություն՝ կախված մուտքային արժեքների չափից: Այդ դեպքում տիեզերական բարդության մեջ այն կլինի O(1):
Ենթադրենք, որ ալգորիթմը պահանջում է մուտքային արժեքների նույն քանակությամբ լրացուցիչ հիշողություն: Այդ դեպքում տիեզերական բարդության մեջ այն կլինի O(n):
Եվ այսպես շարունակ։
