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
51
Vastaukset
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 742962
- 682837
- 681822
Tykkään susta
Elämäni loppuun asti. Olet niin suuresti siihen vaikuttanut. Tykkäsit tai et siitä171679- 241657
- 261602
- 201600
- 481297
- 381273
Onko meillä
Molemmilla nyt hyvät fiilikset😢ei ainakaan mulla mutta eteenpäin on mentävä😏ikävä on, kait se helpottaa ajan myötä. Ko91269