Python stazaCjelina 4 · Prvi algoritmiLekcija 25

Zašto je program spor

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 = 0
for i in range(1, n + 1):
    zbroj += i
    koraka += 1
print(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 programaBroj korakaPrimjer iz lekcija
bez petlje, samo račun1formula za zbroj
petlja koja broj stalno dijeli s 2oko log Nkoliko puta prepoloviti
petlja dok je d · d ≤ Noko √Nprost broj, lekcija 11
jedna petlja do NNzbroj, najveći, lekcija 7
sortiranjeoko N · log Nlekcija 19
petlja u petlji do NN · Nsvi 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 = 0
while n > 1:
    n = n // 2
    koraka += 1
print(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?

N2481632641282565121024
log N12345678910

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ženostN = 1000N = 100 000N = 1 000 000 000
O(1)111
O(log N)101730
O(√N)3231631 623
O(N)1000100 000milijarda: presporo
O(N log N)10 0001,7 milijunapresporo
O(N²)milijun10 milijardi: presporopresporo
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 NRješenje koje stižePrimjer
do 20sve mogućnosti, čak i vrlo mnogo njihsve kombinacije
do 1000O(N²): petlja u petljisvi parovi
do 100 000O(N log N) ili O(N)sortiranje, skup, rječnik
do milijardu i višeO(√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:

NaredbaKorakaZašto
x in listado Nprovjerava element po element
x in skup, x in rjecnikotprilike 1lekcija 24
a.count(x), sum(a), max(a)Nprolaze cijelu listu
a.pop(), a.append(x)1rade na kraju liste
a.pop(0), a.insert(0, x)Npomiču sve ostale elemente
a.sort()N log Nlekcija 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?

Pitanje

Python napravi otprilike koliko jednostavnih koraka u sekundi?

Pitanje

Gdje se krije skrivena petlja?

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.

Riješi u evaluatoru

Prepolovi

★☆☆ lagano

Koliko puta treba broj N cjelobrojno podijeliti s 2 (zanemarujući ostatak) da bi postao 1?

Ulaz
Jedan prirodni broj N.
Izlaz
Broj dijeljenja.
Ograničenja
1 ≤ N ≤ 10¹⁸
Ulaz
20
Izlaz
4
Riješi u evaluatoru

Broj djelitelja

★★☆ srednje

Koliko djelitelja ima prirodni broj N?

Ulaz
Jedan prirodni broj N.
Izlaz
Broj djelitelja broja N.
Ograničenja
1 ≤ N ≤ 10¹²
Ulaz
12
Izlaz
6
Ulaz
13
Izlaz
2
Treba ti pomoć?

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.

Riješi u evaluatoru

Upiti

★★★ teže

Zadana je lista od N brojeva. Zatim slijedi Q pitanja: koliko se puta broj x pojavljuje u listi?

Ulaz
U prvom retku N, u drugom N brojeva. U trećem retku Q, u četvrtom Q brojeva x.
Izlaz
Q redaka, u svakom odgovor na jedno pitanje.
Ograničenja
1 ≤ N, Q ≤ 100 000, brojevi su od 1 do 1 000 000 000
Ulaz
6 5 3 5 1 3 5 3 5 2 3
Izlaz
3 0 2
Treba ti pomoć?

a.count(x) za svako pitanje je O(N · Q), to jest do 10 milijardi koraka. Prebroji sve brojeve jednom, u rječnik, pa svako pitanje odgovori odmah.

Riješi u evaluatoru

9Što smo naučili

  • Brzina ovisi o broju koraka: to je složenost (time complexity).
  • Jedna petlja do N je O(N), petlja u petlji O(N²), petlja do korijena O(√N), prepolovljavanje O(log N).
  • log N je broj prepolovljavanja od N do 1; i za milijardu je samo oko 30.
  • Python stigne nekoliko milijuna do desetak milijuna koraka u sekundi.
  • Ograničenja u zadatku otkrivaju koliko brzo rješenje treba.
  • Pazi na skrivene petlje: in na listi, count, pop(0).
Najčešće greške

Petlja tamo gdje treba formula · count ili in lista unutar petlje · zanemarena ograničenja