9: Laskettavuus ja kompleksisuus

Question 1

Kysymys voiko algoritmi selvittää, pysähtyykö tietty ohjelma

Answer 1

Pysähtymisongelma

Algoritmi ei pysty ratkaista ongelmaa, tämä kertoo tietokoneiden rajoittuneisuudesta. Esimerkki algoritmisesti ratkeamattomista ongelmista

Question 2

Tapa, millä algorimeja arvoidaan suoritusajan ja muistin kannalta

Answer 2

Algoritmien analyysi

Suoritusajan ja vaaditun muistitilan perusteella algoritmeja jaetaan eri kompleksisuusluokkiin

Question 3

Algoritmien kompleksisuusluokka, jossa resurssivaatimus kasvaa suoraan riippuen syötteen koosta

Answer 3

Lineaarinen kompleksisuus

O(n)

Question 4

Algoritmien kompleksisuusluokka, jossa resurssivaatimus kasvaa logaritmisessa suhteessa syötteen kokoon

Answer 4

Logaritminen kompleksisuus

O(logn)

Question 5

Algoritmien kompleksisuusluokka, jossa resurssivaatimus kasvaa neliöllisessä suhteessa syötteen kokoon

Answer 5

Neliöllinen kompleksisuus

O(n^2)

Ilmenee epätehokkaassa kuplalajittelussa

Question 6

Algoritmien kompleksisuusluokka, jossa resurssivaatimus kasvaa loglineaarisessa suhteessa syötteen kokoon

Answer 6

Loglineaarinen kompleksisuus

O(nlogn)

Pikalajittelussa on loglineaarinen kompleksisuus

Question 7

Algoritmien kompleksisuusluokka, jossa resurssivaatimus kasvaa eksponentiaalisessa suhteessa syötteen kokoon

Answer 7

Eksponentiaalinen kompleksisuus

O(n!)

Esim. kauppamatkaajan ongelma