Нотацияи бузург 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 барои интихоби алгоритмҳои самаранок ва сохторҳои додаҳо дар вақти таҳия муҳим аст.