Algoritmi → Složenost algoritama → Složenost algoritama: koliko brzo radi program?

Složenost algoritama: koliko brzo radi program?

Lekcija 1 od 4 · Složenost algoritama

Dva tačna programa mogu da rade potpuno različito vreme: jedan za delić sekunde, a drugi satima. Složenost opisuje kako vreme rada raste kada raste ulaz. Kada je znamo, pre pisanja programa možemo da procenimo da li će rešenje stići u vremensko ograničenje zadatka.

Pre nego što počneš: potrebno predznanje – petlje, nizovi.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Brojanje operacija

Ne merimo sekunde (zavise od računara), već broj osnovnih koraka u zavisnosti od veličine ulaza n. Pogledajmo tri načina da se izračuna zbir 1 + 2 + … + n:

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    // 1) jedna petlja: n sabiranja – O(n)
    long long s1 = 0;
    for (long long i = 1; i <= n; i++) s1 += i;

    // 2) dve petlje: dodajemo 1 po 1 – oko n²/2 sabiranja – O(n²)
    long long s2 = 0;
    for (long long i = 1; i <= n; i++)
        for (long long j = 1; j <= i; j++) s2++;

    // 3) formula: tri operacije bez obzira na n – O(1)
    long long s3 = n * (n + 1) / 2;

    cout << s1 << " " << s2 << " " << s3 << endl;
    return 0;
}

Za n = 109 prvi način radi oko sekunde, drugi bi trajao vekovima, a treći je trenutan.

O-notacija

Kažemo da algoritam ima složenost O(f(n)) ako je broj koraka najviše srazmeran sa f(n). Konstante i manji sabirci se zanemaruju: 3n² + 5n + 7 koraka je O(n²), jer za veliko n dominira n².

SloženostNazivTipičan primer
O(1)konstantnaformula, pristup a[i]
O(log n)logaritamskabinarna pretraga, brzo stepenovanje
O(√n)korenskaprovera da li je broj prost (delioci do √n)
O(n)linearnajedan prolaz kroz niz
O(n log n)„n log n“sortiranje
O(n²)kvadratnadve ugnježdene petlje, svi parovi
O(n³)kubnatri petlje, Floyd-Warshall
O(2ⁿ)eksponencijalnasvi podskupovi, bektreking
O(n!)faktorijelnasve permutacije

Procena iz ograničenja zadatka

Računar uradi oko 108 prostih operacija u sekundi. Iz ograničenja za n u postavci zato se skoro uvek vidi kakvo rešenje se očekuje:

OgraničenjeNajsporija složenost koja prolazi (≈1 s)Šta to obično znači
n ≤ 10–11O(n!)sve permutacije
n ≤ 20–25O(2ⁿ)svi podskupovi, bektreking
n ≤ 500O(n³)tri petlje, DP sa tri indeksa
n ≤ 5 000O(n²)dve petlje, DP sa dva indeksa
n ≤ 106O(n log n)sortiranje, binarna pretraga, priority_queue
n ≤ 108O(n)jedan prolaz, prefiksne sume
n ≤ 1018O(log n) ili O(1)formula, binarna pretraga po odgovoru, brzo stepenovanje
Primer: „dato je n ≤ 200 000 brojeva, ispiši koliko parova ima zbir K“. Dve petlje bi bile 2·1010 koraka – prespor. Treba O(n log n): sortiranje + dva pokazivača ili binarna pretraga.

Kako odrediti složenost koda

  • Uzastopni delovi se sabiraju, a veći dominira: O(n) + O(n²) = O(n²).
  • Ugnježdene petlje se množe: petlja do n unutar petlje do n je O(n²).
  • Petlja u kojoj se promenljiva deli ili množi sa 2 ima O(log n) koraka: while (n > 0) n /= 2;
  • Poziv bibliotečke funkcije ima svoju složenost: sort je O(n log n), s.insert u set O(log n), v.erase(v.begin()) nad vektorom O(n)!
// koliko cifara ima broj n u binarnom zapisu? – O(log n)
int cifre = 0;
while (n > 0) {
    n /= 2;
    cifre++;
}
Zamka: for (int i = 0; i < s.size(); i++) s = s + "x"; izgleda kao jedna petlja, ali svako sabiranje stringova kopira ceo string – ukupno O(n²). Isto važi za v.insert(v.begin(), x) i brisanje sa početka vektora.

Memorijska složenost

I memorija je ograničena (obično 64–256 MB). Niz od 107 brojeva tipa int zauzima 40 MB, a tipa long long 80 MB. Matrica int a[10000][10000] zauzima 400 MB – prevelika. Zato se pazi i na memorijsku složenost: O(n) memorije je skoro uvek u redu, O(n²) samo za n do nekoliko hiljada.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Lako

Koliko puta se izvrši?

Za dati broj n (1 ≤ n ≤ 1018) ispiši koliko puta se izvrši telo petlje for (i = 1; i <= n; i *= 2).

Primer 1

Ulaz

1

Izlaz

1

Primer 2

Ulaz

8

Izlaz

4

Primer 3

Ulaz

1000000000000000000

Izlaz

60
ZADATAK 02Težina: Srednje

Parovi sa zbirom K – brzo

Dato je n ≤ 2·105 različitih celih brojeva i broj K. Ispiši koliko ima parova (neuređenih) sa zbirom tačno K. Rešenje O(n²) je prespor.

Primer 1

Ulaz

6 10
1 9 3 7 5 2

Izlaz

2

Primer 2

Ulaz

3 4
2 1 3

Izlaz

1
Česte greške i saveti
  • U postavci zadatka uvek prvo pogledaj ograničenja – ona otkrivaju očekivanu složenost.
  • Zbir ili proizvod velikih brojeva čuvaj u long long; složenost ne pomaže ako je rezultat pogrešan zbog prekoračenja.
  • Bibliotečke funkcije nisu „besplatne“ – proveri njihovu složenost.

Proveri znanje

Otvori kviz

Složenost algoritama

1. Kolika je složenost dve ugnježdene petlje do n?




2. Ograničenje je n ≤ 10⁶. Koja složenost sigurno prolazi za oko sekundu?




3. Kolika je složenost petlje while (n > 0) n /= 2;?




4. Koliko operacija u sekundi otprilike uradi računar?