Amúgy az a sejtésem, hogy a fentinél jobb algoritmust csak úgy lenne lehetséges írni, ha ismernénk az n-edik prímet meghatározó függvényt. Gyanítom, hogy enélkül esélytelen a fentinél gyorsabb algoritmust adni a problémára, de hátha valakinek mégis eszébe jut valami. ;-)

Ugye jól értem, hogy a 4. lépés közepe az, hogy "Legyen q=q+1 és p=1"?

Egyébként mi a gyakorlati alkalmazás?

Ja és a naiv algoritmus nem O(n) hanem O(n^2), ha tényleg ellenőrzöd berakáskor, hogy a szám már a listában van-e....

Igen, úgy értettem.

Az ellenőrzés maga nem O(n) nagyságrendű, ugyanis a konstrukcióból (szerintem) következik, hogy p/q akkor és csak akkor eleme a listának, ha p és q relatív prímek, vagyis az "ellenőrzöm, hogy benne van-e már a listában" ekvivalens annak az eldöntésével, hogy p és q relatív prímek, ez pedig általában kevesebb, mint O(n) lépésben eldönthető (a megoldás, amit ismerek – bináris euklideszi algoritmus –, legrosszabb esetben a nagyobbik szám bitjeinek a számával négyzetesen arányos rendű, vagyis csak n>36 esetén lesz gyorsabb, mint O(n)). De tény, valóban rosszabb a naív algoritmus, mint O(n).

Igazából ezt nem a gyakorlati felhasználás miatt kérdeztem, csak a reggeli kutyaséta közben jutott eszembe a probléma. Amúgy az inspirált, hogy frekvencia- és amplitúdó-modulációnál az, hogy milyen hangszínt kap az ember, azzal függ össze, hogy a moduláló- és vivőfrekvenciák aránya milyen (minél kisebb nevezőjű racionális, annál "harmonikusabb" a hangszín). Azon kezdtem el agyalni, hogy hogy tudnék az egyik példaprogramba beilleszteni egy olyan csúszkát, ahol a csúszka egyik vége 1, a másik vége meg valami batár nagy nevezőjű racionális szám, és az átmenet viszonylag folytonosan megy végig a "hangszíntérben" (vagyis, a fent leírt módszer szerint megy végig a racionális számokon).

Természetesen a gyakorlatban ezt táblázatos kiolvasással fogom implementálni, mivel a csúszka-objektum, amit a Max kínál, amúgy is diszkrét értékeket ad vissza – az isten (jelen esetben, Miller Puckette) is arra teremtette, hogy táblázatból olvasson ki értékeket. Inkább csak "elgondolkodtató érdekességként" jutott eszembe, hogy ha nem a táblázatban eltárolásra szavaznék, akkor vajon hogyan lehetne egy gyors algoritmust írni a problémára? Szóval a problémafelvetés inkább elméleti...

Szerintem ezt nem lehet O(1) alatt megoldani. Nincs erre bizonyításom, csak egy olyan heurisztikám, hogy nagyon hasonlít a prímfelbontásra amit szintén nem tudunk megoldani.

Viszont létezik olyan megszámoló algoritmus, ami nem optimális (ugyanazt a számot többször számolja), viszont tényleg O(n) a megszámolás és O(1) a sorszám keresés. Érdekel?

For the record, írd le. :-)

A konkrét felhasználás szempontjából az fontos, hogy a számok pontosan abban a sorrendben jöjjenek, mint a fenti buta algoritmussal (vagyis, ha azt mondom, hogy a 6. elemet kérem, akkor valóban 3/4-et kapjak vissza, és ne 2/4-et), de mondom, a konkrét szoftverben ezt nagy valószínűséggel táblázatos kiolvasással fogom megoldani, mivel memória van bőven, és a táblázatos kiolvasásnál gyakorlatilag semmi sem gyorsabb.

q > p > 0

n = q * (q+1) / 2 + p;