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
61
Vastaukset
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Nainen kokki autossa kammottavan kuoleman sähköauto-Teslan syttyessä tuleen.
https://www.is.fi/autot/art-2000011652873.html Näin vaarallisia sähköautopalot voivat olla.845167Persuja ei aluevaltuustoissa näy
Ei tunnu persuja paljon paikalliset asiat kiinnostavan, vaan ainoastaan ulkomaalaiset, joku Israel ja Trumpin fanitus.263488Päivän Riikka: Uudenkaupungin autotehdas hiljeni
Näin ne 100 000 uutta pysyvää ei-tempputyötä yksityiselle sektorille tämän hallituksen ansiosta syntyy. Työntekijöille j382838Riikka vie Suomen kohta ykköseksi työttömyyskisassa
Espanja: 10,5 % Suomi: 10,3 % Ruotsi: 9,3 % Kisa on tiukkaa, mutta Riikalla hyvä draivi päällä. Vasemmistolaisen päämin162011Kerro kaivattusi nimi tai nimikirjaimet
🌠 Tähdenlento! Kirjoittamalla kaivattusi nimen tai nimikirjaimet tähän, saattaa toiveesi toteutua.581820- 471586
Alkuvuodesta poistuu työttömyyskorvaus kaikilta joilla on säästössä rahaa
Tippuu korvaukselta iso määrä työttömiä.2721523- 941382
Tämmönen höpsö
Höpönassu mä olen. En mikään erikoinen…hölötän välillä ihan levottomia. Tykkäisit varmasti jos olisin siellä sun vieress441366Hiljaisuus
Tarkoittaa välinpitämättömyyttä, henkistä väkivaltaa ja kiusaamista. Olet valinnut hiljaisuuden.731078