Keskustelu: Yleinen keskustelu: Aikakompleksisuus

Miten laskea algoritmin aikakompleksisuus?

Voit lukea aiheesta Wikipediasta tai jostain tekstikirjasta.

Jos tarvitset apua jonkun tietyn algoritmin kanssa, kerro ihmeessä mikä algoritmi on kyseessä.

Vaikka ihan, joku kertoma esim.--> Vaikka tämä pseudokoodi:)

i := 1
WHILE n>1 DO
  i := i*j
  n := j–1
ENDWHILE
RETURN i

Yksinkertaisten asioiden kuten kerto- ja yhteenlaskun oletetaan yleisesti vievän vakiomäärä aikaa eli O(1). Jokaisella silmukan kierroksella tehdään vakiomäärä O(1)-asioita, joten yhden kierroksen aikakompleksisuus on c * O(1) = O(1). Kierroksia on n-1 kappaletta eli kokonaisuudessaan algoritmi on (n-1) * O(1) = O(n).

Usein riittää, että laskee montako silmukkaa on sisäkkäin. :)

OK thx :)

Aikakompleksisuuden asymptoottinen suuruusluokka? Tiedän, että sen määrää potenssin korkein arvo algoritmissa. Tässä pitäisi määritellä T(n) saadakseen selville suuruusluokka?

k := 1
WHILE n > 1 DO
k := k * n
n := n – 1
ENDWHILE
RETURN k
ENDMODULE

Mod. lisäsi kooditagit!

Toihan on ihan peruslooppi, aikakompleksisuus O(n)

Grez kirjoitti:

Tosin järkevämpää tuo olisi kirjoittaa ihan vain potenssilaskuna

On kylläkin kertoma eikä potenssi.

Behemot:

1. Käyttäisit jo kooditageja!
2. Turhaan toistat joka kysymyksessäsi samaa koodia.
3. Mikset käy kunnolla sitä kurssiasi? Siellä nämä asiat varmasti opetetaan.
4. Koeta kysyä selvemmin. Mikä ihmeen T(n)?

Koodissasi selvästi käydään silmukassa noin n kierrosta, ja jos lukujen kokoa ei ole rajoitettu, pitää lisäksi huomioida, että kertolasku hidastuu lukujen kasvaessa.

Metabolix kirjoitti:

On kylläkin kertoma eikä potenssi.

Joo ehdin juuri huomata itsekin :)

Miten tämä kirjoitetaan potenssilaskuksi?

Lisäys: Ok:) Sain jo asiasta kiinni :)

Behemot kirjoitti:

Miten tämä kirjoitetaan potenssilaskuksi?

Juu siis kyseessä ei tietenkään ollut potenssi vaan kertoma. Sori että aiheutin ihan turhaa hälinää tähän ketjuun. Pitäisi oikeasti lukea se koodi ennen kuin vastaa.

( Jos nuo on kokonaislukuja niin tuosta sais O(1) kompleksisen käyttämällä taulukkoa. 32-bit luvuille riittää 12 ja 64-bit luvuille 20 arvoa :D )