Vodič · Algoritmi · Složenost algoritama
Složenost algoritama – vodič kroz lekcije
Tačno rešenje nije dovoljno – mora biti i dovoljno brzo. Ova oblast uči kako se procenjuje brzina programa pre nego što se pokrene i kako se sporo rešenje pretvara u brzo.
Počinje se od O-notacije i čitanja ograničenja iz postavke, nastavlja formulama koje zamenjuju petlje, a završava tipičnim optimizacijama.
- 6–8. razred i srednja škola
- C++
- Priprema za takmičenja
Zašto je ovo važno za takmičenje: skoro svaki zadatak ima ograničenja za
n. Iz njih se, pre pisanja koda, vidi da li je dovoljna petlja, treba li sortiranje ili postoji formula – vidi tabelu u lekciji Složenost algoritama.
1 Složenost
Kako se meri i procenjuje brzina algoritma.
2 Formule umesto petlji
Kada se rezultat petlje može izračunati odmah.
Zamena iteracija formulom
Aritmetički niz, kombinatorne formule, segmenti u binarnom stringu.
Otvori lekciju →Formule za zbirove i brojanje
Zbirovi, deljivi u intervalu, uključenje–isključenje, brojanje po grupama.
Otvori lekciju →Zamena iteracija formulom – zadaci
Zbirka zadataka u kojima formula zamenjuje petlju.
Otvori lekciju →3 Ubrzavanje rešenja
Tipični načini da se sporo rešenje ubrza.
Predloženi redosled
Korisni spoljni resursi
- USACO Guide – Time Complexity – složenost sa primerima (engleski)
- CSES Problem Set – „Introductory Problems“ – zadaci u kojima formula zamenjuje petlju