Ինչպե՞ս գնահատել ալգորիթմի բարդությունը կամ որոշել նրա ասիմպտոտիկը։

Անհրաժեշտ է գնահատել ալգորիթմի բարդությունը, օգտագործելով ասիմպոտիկ վերլուծություն, որը թույլ է տալիս նկարագրել ալգորիթմի արդյունավետությունը մուտքային տվյալների չափի ($n$) կախված։ հիմնական քայլերը:

1. Հիմնական գործողությունների սահմանում։ Ընտրվում են այն գործողությունները, որոնց կատարման ժամանակը զգալիորեն կախված է $n$-ից (օրինակ՝ համեմատություններ, նշանակումներ, թվաբանական գործողություններ):
2. Գործողությունների քանակի հաշվարկ։ Հաշվարկվում է հիմնական գործողությունների քանակը կախված $n$-ից։ Դա կարող է լինել ճշգրիտ բանաձև կամ գնահատում:
3. Ասիմպոտիկ դասի սահմանում։ Օգտագործվում են մեծ O ($O$), Омեգա ($\Omega$) և Թեթա ($\Theta$) նշումները՝ նկարագրելու վերին, ներքևի և ճշգրիտ ասիմպոտիկ վարքագիծը:

• $O(f(n))$: Ալգորիթմը կատարվում է ժամանակ, որը չի գերազանցում կոնստանտը, բազմապատկված $f(n)$-ով, մեծ $n$-ի դեպքում։ Օգտագործվում է ամենավատ դեպքի նկարագրության համար։
• $\Omega(f(n))$: Ալգորիթմը կատարվում է ժամանակ, որը չի պակասում կոնստանտից, բազմապատկված $f(n)$-ով, մեծ $n$-ի դեպքում։ Օգտագործվում է ամենալավ դեպքի նկարագրության համար։
• $\Theta(f(n))$: Ալգորիթմը կատարվում է ժամանակ, պրոպորցիոնալ $f(n)$-ին, մեծ $n$-ի դեպքում։ Օգտագործվում է միջին դեպքի կամ երբ լավագույն և ամենավատ դեպքերը ունեն նույն ասիմպոտիկ կարգը։

Ամենից հաճախ օգտագործվում է Մեծ $O$՝ ժամանակի վերին սահմանը նկարագրելու համար, ինչը կարևոր է ալգորիթմի մասշտաբայնության հասկանալու համար ամենավատ սցենարում։

4. Կոնստանտների և ցածր կարգի անդամների անտեսում։ Ասիմպոտիկ սահմանման ժամանակ անտեսվում են կոնստանտային գործակիցները և ցածր կարգի անդամները, քանի որ մեծ $n$-ի դեպքում գերակշռում է ամենամեծ ցուցանիշով ֆունկցիան։ Օրինակ՝ $3n^2 + 5n + 10$ դեպքում ասիմպոտիկը կլինի $O(n^2)$։

Տիպիկ ասիմպոտիկ դասեր (աճման կարգով):

• $O(1)$: Կոնստանտային բարդություն (ժամանակը կախված չէ $n$-ից):
• $O(\log n)$: Լոգարիթմական բարդություն (ժամանակը շատ դանդաղ աճում է $n$-ի հետ, բնորոշ է բինարային որոնման ալգորիթմներին):
• $O(n)$: Գծային բարդություն (ժամանակը ուղղակի proportional է $n$-ին, բնորոշ է պարզ որոնմանը):
• $O(n \log n)$: Գծային-լոգարիթմական բարդություն (հատկապես արդյունավետ դասավորող ալգորիթմների համար, ինչպիսիք են Quick Sort կամ Merge Sort):
• $O(n^2)$: Քվադրատային բարդություն (ժամանակը աճում է $n$-ի քառակուսով, բնորոշ է պարզ դասավորող ալգորիթմներին, ինչպիսիք են Bubble Sort):
• $O(n^c)$ (կամ $c > 1$): Պոլինոմային բարդություն:
• $O(c^n)$ (կամ $c > 1$): Էքսպոնենտային բարդություն (ժամանակը շատ արագ աճում է $n$-ի հետ, բնորոշ է բոլոր հնարավոր տարբերակների որոնմանը):
• $O(n!)$: Ֆակտորիալ բարդություն (ամենաբարձր դասը, աճում է շատ արագ):

Ասիմպոտիկ դասերի որոշման համար ցիկլային կառուցվածքների համար:

• Հետևական կոդի բլոկներ: Բլոկների բարդությունը գումարվում է։ $O(A+B) = O(\max(A, B))$:
• Ներքին ցիկլեր: Իտերացիաների թիվը բազմապատկվում է։ $O(n \times m)$։ Եթե $m=n$, բարդությունը $O(n^2)$ է:
• Տվյալների մուտքի չափի նվազեցմամբ ցիկլեր: Օրինակ՝ բաժանում 2-ով յուրաքանչյուր իտերացիայի ժամանակ, ինչը հանգեցնում է լոգարիթմական բարդության ($O(\log n)$):

Օրինակ:

Պարզ զանգվածի որոնում:

# Հիմնական գործողությունների հաշվարկ (համեմատություններ, նշանակումներ)
# Այս դեպքում հիմնական գործողությունը - համեմատում ցիկլում
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 նշանակում (ցիկլից դուրս)
    for i in range(1, len(arr)): # Ցիկլը կատարվում է $len(arr) - 1$ անգամ
        # Ցիկլի ներսում:
        # 1 համեմատում (if arr[i] > max_val)
        # հնարավոր է 1 նշանակում (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Եթե զանգվածի չափը $n = \texttt{len(arr)}$, ապա ցիկլը կատարվում է $n-1$ անգամ։ Ամեն մի կրկնության մեջ կատարվում է կոնստանտային քանակի գործողություններ։ Ընդհանուր գործողությունների թիվը պրոպորցիոնալ է $n$-ին։ Ասիմպոտիկ բարդությունը: $O(n)$։

Օրինակ՝ ներդրված դասավորություն (Insertion Sort)

# Հիմնական գործողությունների հաշվարկ
# Հիմնական գործողություններ՝ համեմատություններ և նշանակումներ/շարժումներ
def insertion_sort(arr):
    # Բացակող ցիկլը կատարվում է $n-1$ անգամ
    for i in range(1, len(arr)):
        key = arr[i] # 1 նշանակում
        j = i - 1 # 1 նշանակում
        # Ներքին ցիկլը կատարվում է ամենավատ դեպքում $i$ անգամ
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 նշանակում (շարժում)
            j -= 1 # 1 հանածո և 1 նշանակում
        arr[j + 1] = key # 1 նշանակում

Բացակող ցիկլը կատարվում է $n-1$ անգամ։ Ամենավատ դեպքում (մասիվը հակառակ կարգով), ներքին ցիկլը միջինում $i/2$ անգամ (կամ մինչև $i$ անգամ)։ Ընդհանուր, բոլոր կրկնությունների համար, ներքին ցիկլի գործողությունների քանակը՝ $1 + 2 + ... + (n-1) \approx n^2/2$։ Ասիմպոտիկ բարդությունը: $O(n^2)$ ամենավատ և միջին դեպքերում, $O(n)$ լավագույն դեպքում (երբ զանգվածը արդեն դասավորված է): Հաճախ գնահատումներում հաշվի են առնում ամենավատ դեպքը (Մեծ $O$):