Какво е нотацията голямо O?

Обозначението Big O (Big O) е математическа нотация, използвана за описание на асимптотичното поведение на функция и горната й граница. В контекста на разработката на софтуер тя се прилага за оценка на производителността на алгоритмите по отношение на консумацията на време (сложност по време) и памет (сложност по място), с нарастване на размера на входните данни. Тя описва най-лошия сценарий на изпълнение.

Най-често срещаните класове на времевата сложност:

• O(1): Постоянно време. Времето за изпълнение не зависи от размера на входните данни.
• O(log n): Логаритмично време. Времето за изпълнение расте бавно с увеличаване на размера на входните данни (например, двоично търсене).
• O(n): Линейно време. Времето за изпълнение е пропорционално на размера на входните данни (например, линейно търсене).
• O(n log n): Линейно-логаритмично време. Често се среща в ефективни алгоритми за сортиране (например, бързо сортиране, сливане).
• O(n^2): Квадратно време. Времето за изпълнение расте пропорционално на квадрата на размера на входните данни (например, мехурно сортиране, сортиране по избор).
• O(2^n): Експоненциално време. Времето за изпълнение расте много бързо с увеличаване на размера на входните данни. Често се среща при пълно претърсване.

Примери за код и тяхната времева сложност:

// O(1)
int първиЕлемент = масив[0];

// O(n)
for (int i = 0; i < масив.length; i++) {
    // някаква операция
}

// O(n^2)
for (int i = 0; i < масив.length; i++) {
    for (int j = 0; j < масив.length; j++) {
        // някаква операция
    }
}

Обозначението Big O се фокусира върху доминиращия член в израза и игнорира константите и по-малко значимите членове, тъй като при големи входове техният принос става незначителен. Например алгоритъм с сложност O(2n^2 + 5n + 10) се счита за O(n^2).

Разбирането на Big O е важно за избора на най-ефективните алгоритми и структури от данни при разработката.