Oletteko sellaista miettineet, että jos meillä on O(n^k) -algoritmi, missä k>1, niin puolittamalla n, n^k tulee (0.5)^k kertaiseksi ja tämähän on pienempi kuin puoli, kun k>1? Jos nämä puolikkaat saadaan yhdistettyä koko tehtävän ratkaisuksi tarpeeksi nopeasti (lineaarisessa ajassa(?)), niin saadaan tehokkaampi algoritmi kuin O(n^k). Tästähän esim. merge- ja quick-sortit saavat voimansa: siitä että "tavallinen" sortti on O(n^2) ja puolittamalla n, aika menee neljäsosaan.
O(n2) ja puolitus
0
81
Vastaukset
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Haluan sinut, kuuletko minua.
Haluan sinut. Toivon, että voisimme olla yhdessä. Mietin pystynkö täyttämään toiveesi, olemaan arvoisesi. Voisitko saad841349- 52977
Alastomat miehet seksikeinussa lasten nähden PRIDEssä!
https://www.iltalehti.fi/kotimaa/a/adf62289-a0b6-4b4c-9672-9e19c01beb51 Eikö nyt muka mene jo aivan liian pitkälle että370808- 142759
- 55699
Anteeksipyynnöstä
Uskotko anteeksipyynnön voimaan? Mikä tekee anteeksipyynnöstä vaikeaa? Onko se mielestäsi joskus turhaa, joko pyytäjän123692- 51658
Naiselle Kuuleppa Tämä
Tämä ei ole mikään vitsi. Minulla on ikävä sinua nainen! Naiselle mieheltä38625- 76612
- 56604