Kas ir lielo O nešana?

Lielā O (Big O) nešana ir matemātiska zīme, kas tiek izmanto funkcijas asimptotiskās uzvedības un tās augšējās robežas aprakstīšanai. Programmatūras izstrādes kontekstā tā tiek izmantota algoritmu veiktspējas novērtēšanai, ņemot vērā laiku (laika sarežģītību) un atmiņu (vietas sarežģītību), palielinoties ievades datu apjomam. Tā apraksta sliktāko scenāriju:

Visbiežāk sastopamās laika sarežģītības klases:

• O(1): Pastāvīgs laiks. Izpildes laiks nav atkarīgs no ievades datu apjoma:
• O(log n): Loģaritmisks laiks. Izpildes laiks lēni pieaug, palielinoties ievades datu apjomam (piemēram, binārā meklēšana):
• O(n): Līnijas laiks. Izpildes laiks ir tieši proporcionāls ievades datu apjomam (piemēram, vienkārša meklēšana):
• O(n log n): Līnijas laiks. Bieži sastopams efektīvos šķirošanas algoritmos (piemēram, ātra šķirošana, sapludināšanas šķirošana):
• O(n^2): Kvadrātiskais laiks. Izpildes laiks pieaug proporcionāli kvadrātam no ievades datu apjoma (piemēram, burbuļšķirošana, izvēles šķirošana):
• O(2^n): Eksponenciālais laiks. Izpildes laiks ļoti strauji pieaug, palielinoties ievades datu apjomam. Bieži sastopams pilnas meklēšanas uzdevumos:

Koda piemēri un to laika sarežģītība:

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

// O(n)
for (int i = 0; i < array.length; i++) {
    // kāda operācija
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // kāda operācija
    }
}

Lielā O nešana koncentrējas uz izteiksmes dominējošo locekli un ignorē konstantes un mazāk nozīmīgus locekļus, jo lielu ievades datu gadījumā to ieguldījums kļūst nenozīmīgs. Piemēram, algoritms ar sarežģītību O(2n^2 + 5n + 10) tiek uzskatīts par O(n^2).

Big O izpratne ir svarīga, izvēloties visefektīvākos algoritmus un datu struktūras programmēšanas laikā.