Viikko 2: Tiivistelmä

Tämän viikon tehtävien aiheena on:

Logaritmi

Logaritmi log_k(x) ilmaisee, montako kertaa luku x täytyy jakaa luvulla k, ennen kuin päästään lukuun 1 tai sen alle.

Esimerkiksi log₂(16) = 4, koska 16 täytyy jakaa 2:lla 4 kertaa:

16 → 8 → 4 → 2 → 1

Monen algoritmin toiminta perustuu puolittamiseen, jolloin 2-kantainen logaritmi (log₂) liittyy algoritmin aikavaativuuteen. Usein tietojenkäsittelyssä alaindeksi 2 jää pois ja log tarkoittaa samaa kuin log₂.

Tärkeä asia on, että log(x) on hyvin pieni, kun x on syötteen koko tms. Esimerkiksi log(10⁶) on vain noin 20 ja log(10⁹) on vain noin 30. Niinpä jos logaritmi esiintyy aikavaativuudessa, sen voi jättää lähes huomiotta eli O(n log n) on lähes yhtä nopea kuin O(n).

Järjestäminen

Yleisin syy logaritmin esiintymiseen aikavaativuudessa on, että algoritmi järjestää jotain. Tehokkaiden järjestämisalgoritmien aikavaativuus on O(n log n).

Tutustumme järjestämisalgoritmeihin pintaa syvemmältä kurssin loppuosassa, ja tällä hetkellä riittää tietää, että Javan komentoja Arrays.sort ja Collections.sort voi käyttää järjestämään tehokkaasti taulukko tai ArrayList. Niistä on hyötyä tämän viikon TMC-tehtävissä...

Logaritmi muualla

Logaritmi esiintyy algoritmeissa myös seuraavissa yhteyksissä:

• binäärihaussa, joka lienee tuttu ohjelmoinnin peruskursseilta
• puurakenteissa (tulee myöhemmin tällä kurssilla)
• kekorakenteessa (tulee myöhemmin tällä kurssilla)
• erikoisemmissa tilanteissa kuten tämän viikon laskarien tehtävä 5

Nämäkin tilanteet liittyvät yleensä jollain tavalla järjestämiseen, kuten tulemme huomaamaan myöhemmin.

Usein tehtävän voi ratkaista suoraviivaisesti ajassa O(n²), mutta haasteena on löytää tehokkaampi ratkaisu ajassa O(n log n). Kun logaritmi ilmestyy kuvioihin, on syytä juhlaan, koska O(n log n) on huomattavasti nopeampi algoritmi kuin O(n²).