Tvoj program je točan, a evaluator javlja „Vrijeme isteklo“. Zašto? Danas učimo procijeniti koliko koraka program napravi i prije nego što ga pokreneš.
Pythonoko 45 minuta4 zadatka za evaluator
1Isti zadatak, dva rješenja
Koliki je zbroj brojeva od 1 do N? Znamo dva rješenja. Prvo je petlja iz lekcije 7. Drugo je formula koju je, prema priči, kao dječak otkrio matematičar Gauss: 1 + 2 + … + N = N · (N + 1) / 2. Oba daju isti rezultat, ali s vrlo različitim brojem koraka.
Program
n = 1000
zbroj = 0
koraka = 0for i inrange(1, n + 1):
zbroj += i
koraka += 1print(zbroj, "u", koraka, "koraka")
print(n * (n + 1) // 2, "u 1 koraku")
Ispis
500500 u 1000 koraka
500500 u 1 koraku
Za N = 1000 razlika se ne osjeti. Ali za N = 1 000 000 000 000 petlja bi trebala bilijun koraka. Python bi je izvršavao danima, a formula daje rezultat odmah.
Ključna ideja
Brzina programa ne ovisi samo o računalu, nego najviše o tome koliko koraka program napravi. To zovemo složenost (engl. time complexity).
2Kako procijeniti broj koraka
Ne moramo brojati svaki korak. Dovoljno je pogledati petlje:
Oblik programa
Broj koraka
Primjer iz lekcija
bez petlje, samo račun
1
formula za zbroj
petlja koja broj stalno dijeli s 2
oko log N
koliko puta prepoloviti
petlja dok je d · d ≤ N
oko √N
prost broj, lekcija 11
jedna petlja do N
N
zbroj, najveći, lekcija 7
sortiranje
oko N · log N
lekcija 19
petlja u petlji do N
N · N
svi parovi, lekcija 23
Petlja koja broj stalno dijeli s 2 vrlo je brza. Koliko puta treba prepoloviti milijun da dođemo do 1?
Program
n = 1000000
koraka = 0while n > 1:
n = n // 2
koraka += 1print(koraka)
Ispis
19
Samo 19 puta. I za milijardu je to samo 29 puta.
3Što je log N
log N (čitaj: logaritam od N) je odgovor na pitanje: koliko puta treba prepoloviti N da dođemo do 1? Isto je pitati: koliko puta treba udvostručiti 1 da dođemo do N?
N
2
4
8
16
32
64
128
256
512
1024
log N
1
2
3
4
5
6
7
8
9
10
Kad se N udvostruči, log N poraste samo za 1. Zato log N raste jako sporo: za tisuću je oko 10, za milijun oko 20, a za milijardu oko 30.
Stani i razmisli
Zamišljam broj od 1 do 100. Smiješ pitati samo „je li veći od…?“. Koliko pitanja ti najviše treba ako svaki put pitaš za sredinu?
Pogledaj odgovor
Najviše 7. Svako pitanje prepolovi skup mogućih brojeva: 100, 50, 25, 13, 7, 4, 2, 1. To je log 100, otprilike 7. Na toj ideji radi binarno pretraživanje iz lekcije 27.
Ključna ideja
U informatici log N gotovo uvijek znači „koliko puta prepoloviti“, odnosno logaritam s bazom 2. Za procjenu brzine dovoljno je znati da je log N mali broj, čak i kad je N ogroman.
4Zapis O( )
Programeri složenost zapisuju slovom O i zagradama: O(N) znači „otprilike N koraka“, O(N²) „otprilike N · N koraka“. Pogledaj koliko je to koraka za različite N:
Složenost
N = 1000
N = 100 000
N = 1 000 000 000
O(1)
1
1
1
O(log N)
10
17
30
O(√N)
32
316
31 623
O(N)
1000
100 000
milijarda: presporo
O(N log N)
10 000
1,7 milijuna
presporo
O(N²)
milijun
10 milijardi: presporo
presporo
Ključna ideja
Python u sekundi napravi otprilike nekoliko milijuna do desetak milijuna jednostavnih koraka. Sve što je ispod toga, stiže na vrijeme.
5Ograničenja u zadatku otkrivaju rješenje
Ograničenja nisu tu slučajno. Iz najvećeg N možeš pogoditi kakvo se rješenje očekuje:
Najveći N
Rješenje koje stiže
Primjer
do 20
sve mogućnosti, čak i vrlo mnogo njih
sve kombinacije
do 1000
O(N²): petlja u petlji
svi parovi
do 100 000
O(N log N) ili O(N)
sortiranje, skup, rječnik
do milijardu i više
O(√N), O(log N) ili O(1)
do korijena, formula
Ključna ideja
Prije pisanja programa pogledaj ograničenja i procijeni broj koraka svog rješenja. Ako je previše, treba ti bolja ideja, a ne brže računalo.
6Skrivene petlje
Neke naredbe izgledaju kao jedan korak, ali u sebi imaju petlju:
Naredba
Koraka
Zašto
x in lista
do N
provjerava element po element
x in skup, x in rjecnik
otprilike 1
lekcija 24
a.count(x), sum(a), max(a)
N
prolaze cijelu listu
a.pop(), a.append(x)
1
rade na kraju liste
a.pop(0), a.insert(0, x)
N
pomiču sve ostale elemente
a.sort()
N log N
lekcija 19
Pazi
a.count(x) unutar petlje po listi skriveno je O(N²). Za N = 100 000 to je presporo, iako program izgleda kratko. Rječnik iz lekcije 24 prebroji sve u jednom prolazu.
Na natjecanju
Prije pisanja koda pogledaj ograničenja: za N do 105 treba rješenje bez dvije ugniježđene petlje; za N do 1000 dvije petlje su u redu.
Na natjecanju
I samo učitavanje može biti sporo: za stotine tisuća redaka input() je spor. Natjecatelji na početku pišu import sys i input = sys.stdin.readline. Tako učitan redak na kraju ima znak novog retka, pa ga očisti sa strip() (lekcija 16).
7Provjeri se
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Pitanje
Dvije ugniježđene petlje do N = 100 000. Koliko je to koraka?
N · N = 10^10, previše za nekoliko sekundi.
Pitanje
Python napravi otprilike koliko jednostavnih koraka u sekundi?
Reda veličine 10^7.
Pitanje
Gdje se krije skrivena petlja?
Te naredbe prolaze kroz cijelu listu.
8Zadaci
Gaussov zbroj
★☆☆ lagano
Koliki je zbroj svih prirodnih brojeva od 1 do N?
Ulaz
Jedan prirodni broj N.
Izlaz
Zbroj 1 + 2 + … + N.
Ograničenja
1 ≤ N ≤ 1 000 000 000 000
Ulaz
100
Izlaz
5050
Treba ti pomoć?
Za N do bilijun petlja neće stići. Upotrijebi formulu iz dijela 1. Koristi // da rezultat bude cijeli broj.
Djelitelji dolaze u parovima d i N // d, kao u lekciji 11. Dovoljno je ići dok je d · d ≤ N i za svaki pronađeni d brojiti dva djelitelja. Pazi na slučaj kad je d · d = N.