Složenost algoritma — zamena iteracija formulom

Vreme izvršavanja algoritma zavisi i od načina na koji je zadatak rešen, odnosno od broja elementarnih operacija koje je potrebno izvršiti. Neke probleme možemo rešiti pomoću petlji, ali za njih postoji i odgovarajuća formula koja može znatno da ubrza program kada je broj ulaznih podataka veliki.

1. Primer — koliko sportista pretrči poslednjeg dana priprema?

Atletičari učestvuju na pripremama za takmičenje koje traju n dana. Prvog dana sportista pretrči a1 metara, a svakog sledećeg dana pretrči d metara više nego prethodnog dana. Napisati program koji određuje koliko metara sportista pretrči poslednjeg dana priprema.

Iterativno rešenje — pomoću petlje

Prvog dana sportista pretrči a1 metara. Svakog narednog dana na prethodnu vrednost dodajemo d. Promenljiva a u svakom koraku čuva broj metara za tekući dan.

Primer kompletnog programa u jeziku C:

Copy

#include <stdio.h>

int main(void)
{
    int n, a1, d, a;

    // Učitavamo broj dana, pređenu razdaljinu prvog dana i dnevno povećanje.
    scanf("%d%d%d", &n, &a1, &d);

    // Prvog dana sportista pretrči a1 metara.
    a = a1;

    // Preostaje još n - 1 dana, pa toliko puta dodajemo d.
    for (int i = 1; i < n; i++)
    {
        a = a + d;
    }

    // Ispisujemo razdaljinu pretrčanu poslednjeg dana.
    printf("%d\n", a);

    return 0;
}

Na primer, ako su n = 5, a1 = 3 i d = 2, razdaljine po danima su:

3, 5, 7, 9, 11

Poslednjeg, petog dana, sportista pretrči 11 metara. Petlja se izvršava n - 1 puta, jer je početna vrednost a1 već razdaljina za prvi dan.

Rešenje pomoću formule

Brojevi koje sportista pretrči po danima čine aritmetički niz. Prvi član tog niza je a1, a razlika između susednih članova je d.

n-ti član aritmetičkog niza računa se formulom:

a_n = a_1 + (n - 1) · d

Za naš primer dobijamo:

a_5 = 3 + (5 - 1) · 2 = 3 + 8 = 11

Zato umesto petlje možemo direktno da izračunamo odgovor formulom. Program je kraći, a broj računskih operacija ne zavisi od broja dana.

Rešenje u jeziku C:

Copy

#include <stdio.h>

int main(void)
{
    int n, a1, d, an;

    // Učitavamo broj dana, razdaljinu prvog dana i dnevno povećanje.
    scanf("%d%d%d", &n, &a1, &d);

    // Direktno izračunavamo n-ti član aritmetičkog niza.
    an = a1 + (n - 1) * d;

    // Ispisujemo razdaljinu pretrčanu poslednjeg dana.
    printf("%d\n", an);

    return 0;
}

Ako je potrebno izračunati i ukupnu razdaljinu koju je sportista pretrčao tokom svih dana, koristi se formula za zbir prvih n članova aritmetičkog niza:

S_n = n · (a_1 + a_n) / 2

Važno je razlikovati ova dva pitanja: formula za a_n određuje koliko je sportista pretrčao poslednjeg dana, dok formula za S_n određuje koliko je ukupno pretrčao tokom svih dana.

2. Formule iz kombinatorike

U nekim zadacima broj mogućnosti može da se izračuna formulom, bez nabrajanja svih mogućnosti pomoću petlji. Često se koriste varijacije, permutacije i kombinacije bez ponavljanja.

Vrsta	Formula	Značenje
Varijacije bez ponavljanja	V(n, k) = n · (n - 1) · ... · (n - k + 1) = n! / (n - k)!	Bira se i raspoređuje k elemenata od ukupno n; redosled je važan.
Permutacije	P(n) = n! = n · (n - 1) · ... · 1	Raspoređuju se svi elementi; redosled je važan.
Kombinacije bez ponavljanja	C(n, k) = n! / (k! · (n - k)!)	Bira se k elemenata od ukupno n; redosled nije važan.

Kombinacije bez ponavljanja mogu se zapisati i ovako:

C(n, k) = [n · (n - 1) · ... · (n - k + 1)] / k!

U nazivniku se nalazi k!, a ne n!. Ovaj oblik je koristan kada treba izračunati broj načina da se izabere k elemenata od ukupno n elemenata.

3. Primer — broj segmenata u binarnom stringu

Dat je binarni string, odnosno niska koja se sastoji samo od znakova 0 i 1. Odrediti broj segmenata dužine najmanje 2 koji počinju i završavaju se znakom 1. Segment mora biti deo stringa sa uzastopnim znakovima.

Posmatrajmo string:

s = "010010001"

U ovoj niski jedinice se nalaze na pozicijama 2, 5 i 9, ako pozicije brojimo od 1. Svaki par različitih jedinica određuje tačno jedan segment koji počinje i završava se jedinicom. Traženi segmenti su:

0[1001]0001
0100[10001]
0[10010001]

U nizu postoje 3 jedinice. Biramo dve od njih: jednu koja će biti početak segmenta i drugu koja će biti kraj. Zato je broj segmenata jednak broju kombinacija od 3 elementa druge klase:

C(3, 2) = 3! / (2! · (3 - 2)!) = (3 · 2) / (2 · 1) = 3

Ovaj zaključak važi i za stringove drugih dužina: ako string sadrži b jedinica, svaki izbor dve različite jedinice određuje jedan segment. Zato je ukupan broj segmenata:

broj_segmenata = b · (b - 1) / 2

Rešenje pomoću formule — jezik C

Najpre prolazimo kroz uneti string i brojimo koliko u njemu ima jedinica. Zatim primenjujemo formulu b · (b - 1) / 2. Naredni program učitava znakove do kraja reda ili do kraja ulaza.

Copy

#include <stdio.h>

int main(void)
{
    int broj_jedinica = 0;
    int znak;
    long long broj_segmenata;

    // Čitamo znakove sve do kraja reda ili kraja ulaza.
    while ((znak = getchar()) != EOF && znak != '\n')
    {
        // Brojimo jedinice u stringu.
        if (znak == '1')
        {
            broj_jedinica++;
        }
    }

    // Svaki par jedinica određuje jedan traženi segment.
    broj_segmenata = (long long)broj_jedinica * (broj_jedinica - 1) / 2;

    printf("%lld\n", broj_segmenata);

    return 0;
}

Rešenje pomoću formule — jezik C++

U C++ možemo da učitamo celu nisku u promenljivu tipa string i da kroz nju prođemo petljom for. I ovde brojimo jedinice, a zatim direktno izračunavamo broj segmenata formulom.

Copy

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    long long broj_jedinica = 0;
    long long broj_segmenata;

    // Učitavamo binarni string.
    cin >> s;

    // Brojimo koliko jedinica string sadrži.
    for (char c : s)
    {
        if (c == '1')
        {
            broj_jedinica++;
        }
    }

    // Broj segmenata jednak je broju parova jedinica.
    broj_segmenata = broj_jedinica * (broj_jedinica - 1) / 2;

    cout << broj_segmenata << endl;

    return 0;
}

Objašnjenje rešenja

Posle brojanja jedinica imamo vrednost b. Ne moramo da tražimo i ispisujemo svaki segment pojedinačno. Dovoljno je da izračunamo koliko različitih parova jedinica postoji.

Za primer 010010001 dobijamo:

b = 3
broj_segmenata = 3 · (3 - 1) / 2 = 3

Obe verzije koje koriste formulu imaju vremensku složenost O(n), jer kroz string prolazimo jednom da bismo izbrojali jedinice. Dodatni prostor koji zauzimaju promenljive za brojanje je konstantan, ne računajući memoriju potrebnu za samu učitanu nisku u C++ verziji.

Druga varijanta — brojanje pomoću dve petlje

Zadatak može da se reši i tako što za svaku jedinicu tražimo sve jedinice koje se nalaze iza nje. Svaki pronađeni par predstavlja jedan segment. Ovo rešenje je jednostavnije za razumevanje kada se tek uči rad sa petljama, ali je sporije za duge stringove.

Copy

#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[100002];
    size_t n;
    long long broj_segmenata = 0;

    // Učitavamo string; fgets je bezbednija zamena za gets.
    if (fgets(s, sizeof(s), stdin) == NULL)
    {
        return 0;
    }

    // Određujemo dužinu stringa, bez znaka za novi red.
    n = strcspn(s, "\r\n");

    // Biramo prvu jedinicu segmenta.
    for (size_t i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            // Tražimo sve jedinice koje se nalaze iza nje.
            for (size_t j = i + 1; j < n; j++)
            {
                if (s[j] == '1')
                {
                    broj_segmenata++;
                }
            }
        }
    }

    printf("%lld\n", broj_segmenata);

    return 0;
}

Poređenje pristupa

Pristup	Vremenska složenost	Objašnjenje
Brojanje jedinica i formula	O(n)	Jedan prolazak kroz string, a zatim konstantan broj računskih operacija.
Dve ugnježdene petlje	O(n²)	Za svaku jedinicu proveravaju se svi znakovi koji se nalaze iza nje.

Zaključak: kada možemo da prepoznamo matematičku formulu koja odgovara zadatku, često možemo da izbegnemo veliki broj ponovljenih operacija. U ovom primeru formula smanjuje složenost sa O(n²) na O(n).

---