რა არის Big O ნოტაცია?

Մեծ O նշանավորումը (կամ O-notation) — մեթոդ է ֆունկցիայի աբսիմպտոտիկ վարքագիծը նկարագրելու համար, որը ամենից հաճախ օգտագործվում է ալգորիթմների արդյունավետության վերլուծության համար, այսինքն՝ ինչպես է ժամանակը կամ օգտագործվող հիշողության ծավալը մեծանում տվյալների մուտքի չափի հետ:

Հիմնական ասպեկտներ:

• Վերևի սահմանը: O-նշանավորումը նկարագրում է ֆունկցիայի աճի վերևի սահմանը, անտեսելով հաստատունները և փոքր անդամներին: Դա ցույց է տալիս ամենավատ իրավիճակի կատարողականությունը:
• Ասիմպտոտիկ վարքագիծ: Կենտրոնանում է ֆունկցիայի վարքագծի վրա, երբ մուտքային տվյալների չափը մոտենում է անսահմանությանը:
• Ալգորիթմների համեմատում: Ինքնուրույն համեմատում է ալգորիթմները՝ անկախ սարքավորումների կամ ծրագրավորման լեզվի:

Հաճախ հանդիպող բարդության դասերի օրինակներ:

Նոտացիա	Անուն	Նկարագրություն	Օրինակ գործողություն ալգորիթմում
O(1)	Կոնստանտ ժամանակ	Վարող ժամանակը կախված չէ մուտքային տվյալների չափից:	Մասիվի տարրին մուտք գործել ըստ ինդեքսի:
O(log n)	Լոգարիթմական ժամանակ	Վարող ժամանակը աճում է լոգարիթմիկ կերպով տվյալների չափի հետ:	Բինար որոնում դասավորված զանգվածում:
O(n)	Գծային ժամանակ	Վարող ժամանակը համընկնում է տվյալների չափի հետ:	Բոլոր տարրերի պարզ որոնում ցանկում:
O(n log n)	Գծային-լոգարիթմական	Վարող ժամանակը աճում է համապատասխանաբար n * log n:	Արագ դասավորում (միջինում), միացման դասավորում:
O(n^2)	Քառակուսային ժամանակ	Վարող ժամանակը համընկնում է տվյալների չափի քառակուսու հետ:	Բլբուլով դասավորում, ներսի ցիկլեր n տարրերով:
O(2^n)	Էքսպոնենտ ժամանակ	Վարող ժամանակը աճում է էքսպոնենտալ կերպով:	Որոշ լրիվ որոնողական խնդիրներ, օրինակ՝ ճանապարհորդի վաճառականի խնդիր (նավնական իրականացմաններում):

# Օրինակ O(1)
def get_first_element(arr):
    return arr[0] # Վարող ժամանակը հաստատուն է, կախված չէ arr-ի չափից

# Օրինակ O(n)
def find_max(arr):
    max_val = arr[0]
    for element in arr:
        if element > max_val:
            max_val = element
    return max_val

# Օրինակ O(n^2)
def print_pairs(arr):
    for i in arr: # Առաջին ներսի ցիկլ
        for j in arr: # Երկրորդ ներսի ցիկլ
            print(i, j)