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
56
Vastaukset
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Taisit vihdoin ymmärtää
Kuinka hirviö mun silmissä olet/olette. Antaisitte mun vaan nyt olla, että palaudun tästä edes joskus.222754- 1121708
- 171341
- 2451308
Keskisarjan puheet olivat ihmisarvoa alentavia
Purra ilmoitti Lauantai-aamuohjelmassa hyväksyvänsä Keskisarjan puheet. Orpon ilmoitus tänään: "Yksikään hallituspuolue1801300Ulkomaalainen yrittäjä
Minkäs alan yrittäjä tämä herrasmies on/oli? Poliisi epäilee varkautelaista 44-vuotiasta miestä entisen puolisonsa murh191124Laita lyhyt tunniste kaivatullesi
Laita lyhyesti joku avainsana, jolla kaivattusi voi sut tunnistaa🤗65994Kannattaako omaan intuitioon luottaa
Kun minulla on tunne, että se mies tykkää minusta yhtä paljon kuin minä hänestä? Siksi olen näin kauan tätä kaipaamista67953En tiedä sinusta
Mutta minä kaipaan sitä meidän välillä vuosia sitten käytyä "säpinää". Edellytykset oli vaikka mihin, varsinkin kun olet25942Olen niiiin vihainen sille naiselle...
Ymmärrän todellakin sua, jos koet joskus olevasi sodan keskellä. OMG. Anna sun kaikki kestää. Tsemppiä 🙏16917