Hei vaan!

Keskiajalla, silloin alkemistien aikaan, etsittiin niin sanottua filosofin kiveä (eng. philosopher's stone), jolla ajateltiin olevan kyky muuntaa esim. kuparin kullaksi taikka hopeaksi (huomatkaa mahdottomuus). Heräsi kysymys, että mitä voisi olla hyvin siistiä, mutta mahdotonta, tietojenkäsittelyopissa tahi ICT-alassa? Itselleni tuli mieleen dynaaminen joukkorakenne, jonka kaikki kolme perusoperaatiota (joukkoon lisääminen, sieltä poisto ja kysely) kävisivät vakioajassa (veisivät maksimissaan aina saman ajan riippumatta joukossa olevien alkioiden määrästä myös pahimmassa tapauksessa). Esimerkiksi, taulukkoon pohjautuvalle, ei-järjestetylle listalle (mm. JDK:n ArrayList) ovat ominaisia seuraavat aikavaativuudet: lisääminen - O(1), poisto - O(n) ja alkion haku - O(n), missä n on joukossa olevien alkioiden määrä. Toisaalta AVL-puun poisto- ja hakuoperaatiot käyvät "vain" ajassa O(log n), mutta lisäämisoperaatio vie suuremman ajan kuin yllämainitun listan - O(log n).

Tuleeko teille mieleen muuta kivaa & mahdotonta?

CAP-teoreeman särkevä tietokanta: yhtäaikaisesti konsistentti, aina saatavilla sekä ositustolerantti. Tietojenkäpistelevät halunnevat suomentaa termini oikein. :)

Seuraavan viikon lottonumerot laskeva ohjelma.

Mielestäni coderodde:n ongelma on ihan mahdollista toteuttaa, vakioaika vaan täytyy olla riittävän suuri esim. käytettävissä olevaan muistikapasiteettiin nähden. Lisäksi vakioaikaisuus harvemmin on tavoittelemisen arvoinen asia. Mieluummin jättää ne sleepit pois palauttaa ne nopeammin, mitkä pystyy palauttamaan nopeammin.

Ja philosopher's stone on muuten suomeksi yleensä viisasten kivi

Varmasti pystyisi toteuttamaan sellaisen joukkorakenteen, jossa lisäys ja poisto kävisivät ajassa O(1) (algoritmeissa ei rekursiota eikä silmukoita), mutta sellaiseen järjestelyyn ei liity mitään indeksointimahdollisuutta. Tarkoitan tässä, että hakuoperaatio joutuisi suorittamaan joko rekursiota tai toistoa, jolloin aikavaativuusanalyysin mielessä sen pahin tapaus ei kävisi O(1)-ajassa. Toki rekursion syvyyttä ja haarautumisastetta tai toistojen määrä voisi rajoittaa (jolloin laskenta-aikakin olisi ylhäältä rajoitettu), mutta sellaisen joukkorakenteen hakuoperaatio muuttuu ns. Monte Carlo - menetelmäksi eli palauttaa kysytyn alkion todennäköisyydellä p < 1.0, kun joukossa alkaa olla tietty määrä alkioita.

katso http://fi.wikipedia.org/wiki/Hajautustaulu

Tai no, nuo nyt on keskimääräisiä aikavaativuuksia. Muistin käyttöä lisäämällä kuitenkin pysyvät tuossa datan määrän kasvaessa.

NP-täydellisten ongelmien tehokas ratkaiseminen kvanttitietokoneilla, puhumattakaan normaaleista tietokoneista. Kumpikaan ei liene mahdollista, tai pikemminkin, kukaan tiedä miksi, mutta on olemassa hyvä arvaus siitä, miksi sitä ei tiedetä. [1]

[1] http://www.scottaaronson.com/papers/npcomplete.pdf

Tyydyn vastaukseesi. Toisaalta, jos alkioille on määritelty suuruusrelaatio ja sitä kautta joukkorakenteesta ovat myöskin operaatiot predecessor ja successor, niin niiden aikavaativuudet olisivat O(n). Toki me voidaan ylläpitää hajautustaulun entryen välillä linkkejä seuraavaan/edelliseen entryyn, jolloin nuo operaatiot kävisivät vakioajassa (hakisivat vain linkkiä pitkin haettavan alkion), mutta tuolloin lisäysoperaatio joutuisi, uuden alkion lisättäessä, etsimään sille seuraajan ja edeltäjän eli skannaamaan pahimmillaan koko hajautustaulun läpi.

Ilmaisuongelma, eli Expression problem, kaipaisi hyvän ja selkeän ratkaisun.

http://en.wikipedia.org/wiki/Expression_problem

Tässä on kuvattu hauska tietorakenne, joka toteuttaa kokonaislukujoukon operaatiot nopeasti. Lisäksi se osoittaa, että alustamattomasta muistista lukeminen ei aina ole virhe.

http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html