Prvo rešenje koje padne na pamet često je tačno, ali presporo. Ova lekcija pokazuje najčešće načine da se rešenje ubrza – od manjeg broja koraka u petlji, preko pamćenja već izračunatog, do izbora bolje strukture podataka – i kada koja ideja pomaže.
Delioci broja dolaze u parovima d i n / d, a manji od njih je najviše √n. Zato je dovoljno proveravati do korena: O(√n) umesto O(n). Za n = 1012 to je 106 koraka umesto 1012.
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long br = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
br++; // delilac d
if (d != n / d) br++; // i njegov par n/d (ako nije isti, kod kvadrata)
}
}
cout << br << endl;
return 0;
}
Ako se ista vrednost računa više puta u petlji, izračunaj je jednom pre petlje. Ako upiti traže zbirove delova niza – pripremi prefiksne sume. Ako rekurzija računa iste potprobleme – zapamti rezultate (dinamičko programiranje).
| Sporo | Brže | Dobitak |
|---|---|---|
| zbir dela niza petljom za svaki upit | prefiksne sume | O(n·q) → O(n + q) |
for (i = 0; i < strlen(s); i++) | int d = strlen(s); pre petlje | O(n²) → O(n) |
| rekurzivni Fibonači | niz sa zapamćenim vrednostima | O(2ⁿ) → O(n) |
| provera „da li je prost“ za svaki broj do n | Eratostenovo sito | O(n√n) → O(n log log n) |
| Operacija koja se ponavlja | Sporo | Brzo |
|---|---|---|
| „da li je x već viđen?“ | prolaz kroz niz, O(n) | set ili niz brojača, O(log n) / O(1) |
| „koji je trenutno najmanji?“ | traženje minimuma, O(n) | priority_queue, O(log n) |
| „koliko elemenata je ≤ x?“ | brojanje, O(n) | sortiranje + upper_bound, O(log n) |
| brisanje sa početka | vector::erase(begin), O(n) | deque ili queue, O(1) |
| zbir dela niza uz izmene | petlja, O(n) | Fenwick stablo, O(log n) |
Kod velikih ulaza (106 brojeva) i samo učitavanje može da traje predugo. Dve linije na početku main višestruko ubrzavaju cin i cout, a "\n" umesto endl ne prazni izlaz posle svakog reda:
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false); // cin/cout bez usklađivanja sa scanf/printf
cin.tie(nullptr); // cin ne čeka da se cout isprazni
int n;
cin >> n;
long long s = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s += x;
}
cout << s << "\n"; // "\n" umesto endl
return 0;
}
Posle ovih linija ne mešaj cin sa scanf ni cout sa printf.
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Broj je savršen ako je jednak zbiru svojih delilaca manjih od njega (6 = 1 + 2 + 3). Za dati broj n ≤ 1012 ispiši DA ako je savršen, inače NE.
6DA28DA12NE137438691328DADato je n ≤ 2·105 brojeva do 109. Ispiši prvi broj (gledano sleva) koji se već pojavio ranije, ili -1. Rešenje O(n²) je prespor.
6
5 3 9 3 5 133
1 2 3-1d * d <= n koristi long long, inače d * d prekoračuje opseg.endl u petlji sa milion ispisa može da uspori program više od samog računanja.1. Do kog broja je dovoljno tražiti delioce broja n?
2. Šta ubrzava ponovljene upite „zbir od l do r“?
3. Čemu služi ios::sync_with_stdio(false)?