Ի՞նչ է մեծ O նշանավորումը։

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

Ամենատարածված ժամանակային բարդության դասերը՝

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

Կոդի օրինակներ և դրանց ժամանակային բարդությունը՝

// O(1)
int firstElement = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // ինչ-որ գործողություն
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // ինչ-որ գործողություն
    }
}

Մեծ O նշանը կենտրոնանում է արտահայտության գերիշխող անդամի վրա և անտեսում է հաստատունները և քիչ կարևոր անդամները, քանի որ մեծ մուտքային տվյալների դեպքում նրանց ներդրումը նվազում է: Օրինակ՝ բարդությամբ O(2n^2 + 5n + 10) ալգորիթմը համարվում է O(n^2):

Մեծ O- ի ըմբռնումը կարևոր է առավել արդյունավետ ալգորիթմներ և տվյալների կառուցվածքներ ընտրելու համար ծրագրավորման ժամանակ։