Šta je notacija velikog 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 је важно за избор најефикаснијих алгоритама и структура података током развоја.