CSES - Viikon 2 johdanto Tällä viikolla viidessä ensimmäisessä tehtävässä tavoitteena on tehdä tehokas $O(n)$-aikainen algoritmi. Tehtäviä testataan myös suurella syötteellä kokoa $n=10^5$, jolloin on tärkeää, että algoritmi on tehokas.

Vaatimus $O(n)$-aikaisuudesta tarkoittaa käytännössä, että algoritmissa saa olla yksi tai useampi yksittäinen silmukka, jotka käyvät läpi merkkijonon merkit tai listan alkiot. Kuitenkin jos algoritmissa on kaksi sisäkkäistä silmukkaa, sen aikavaativuus on $O(n^2)$, mikä on liian hidasta.

Kuudennessa tehtävässä syötteen koko voi olla $n=10^9$, jolloin jopa $O(n)$-aikainen algoritmi on liian hidas. Tässä tehtävässä haetaan $O(1)$-aikaista algoritmia.