Amarengo

Articles and news

mi okozza egy algoritmus o (log log n) komplexitását?

O(log log n) kifejezések különböző helyeken jelenhetnek meg, de általában két fő útvonal érkezik erre a futási időre.

Négyzetgyökkel történő zsugorodás

amint azt a hivatkozott kérdésre adott válasz említi, az algoritmus időösszetettségének általános módja O(log n) az, hogy az algoritmus úgy működik, hogy az egyes iterációkon ismételten csökkenti a bemenet méretét valamilyen állandó tényezővel. Ebben az esetben az algoritmusnak o(log n) iterációk után kell befejeződnie, mert az O(log n) osztások állandóval történő elvégzése után az algoritmusnak 0-ra vagy 1-re kell csökkentenie a probléma méretét. Ezért van például a bináris keresés bonyolultsága O (log n).

érdekes módon van egy hasonló módszer a probléma méretének csökkentésére, amely o(log log n) formátumú futási időket eredményez. Ahelyett, hogy az egyes rétegeknél felére osztanánk a bemenetet, mi történik, ha az egyes rétegeknél a méret négyzetgyökét vesszük?

vegyük például a 65 536 számot. Hányszor kell ezt elosztanunk 2-vel, amíg le nem jutunk 1-re? Ha ezt megtesszük, megkapjuk

  • 65,536 / 2 = 32,768
  • 32,768 / 2 = 16,384
  • 16,384 / 2 = 8,192
  • 8,192 / 2 = 4,096
  • 4,096 / 2 = 2,048
  • 2,048 / 2 = 1,024
  • 1,024 / 2 = 512
  • 512 / 2 = 256
  • 256 / 2 = 128
  • 128 / 2 = 64
  • 64 / 2 = 32
  • 32 / 2 = 16
  • 16 / 2 = 8
  • 8 / 2 = 4
  • 4 / 2 = 2
  • 2 / 2 = 1

ez a folyamat 16 lépést tesz, és az is igaz, hogy 65,536 = 216.

de, ha vesszük a négyzetgyök minden szinten, megkapjuk

  • √65,536 = 256
  • √256 = 16
  • √16 = 4
  • √4 = 2

figyeljük meg, hogy csak úgy négy lépést, hogy egészen le 2. Miért van ez?

először is, egy intuitív magyarázat. Hány számjegy van az n és az n számokban? Az n számban hozzávetőlegesen log n számjegy van, és hozzávetőlegesen log (^n) = log (n1/2) = (1/2) log n számjegy a (z) n számban. Ez azt jelenti, hogy minden alkalommal, amikor négyzetgyököt vesz, nagyjából felére csökkenti a számjegyek számát. Mivel egy mennyiséget csak felére lehet csökkenteni K O (log k) szor, mielőtt állandóra esik(mondjuk 2), Ez azt jelenti, hogy csak négyzetgyököket vehet fel O (log log n) alkalommal, mielőtt a számot valamilyen állandóra csökkentené (mondjuk 2).

most csináljunk egy kis matekot, hogy ez szigorú legyen. Le ‘ TS átírja a fenti sorrendet két hatványa szempontjából:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

figyeljük meg, hogy követtük a sorrendet 216 → 28 → 24 → 22 → 21. Minden iterációnál felére csökkentjük a kettő hatványának kitevőjét. Ez érdekes, mert ez kapcsolódik vissza ahhoz, amit már tudunk – a K számot csak felére oszthatja O(log k) alkalommal, mielőtt nullára csökken.

tehát vegyünk bármilyen n számot, és írjuk n = 2K-ként. Minden alkalommal, amikor a négyzetgyök nak, – nek n, felére csökkenti a kitevőt ebben az egyenletben. Ezért csak O (log k) négyzetgyökek alkalmazhatók, mielőtt k 1-re vagy alacsonyabbra esik (ebben az esetben n 2-re vagy alacsonyabbra esik). Mivel n = 2K, ez azt jelenti, hogy k = log2 n, ezért a vett négyzetgyökek száma O (log k) = O(log log n). Ezért, ha van olyan algoritmus, amely úgy működik, hogy ismételten csökkenti a problémát Egy méret alproblémára, amely az eredeti probléma méretének négyzetgyöke, akkor az algoritmus az O(log log n) lépések után megszűnik.

ennek egyik valós példája a van Emde Boas fa (vEB-fa) adatszerkezet. A vEB-fa egy speciális adatstruktúra a 0 tartományban lévő egész számok tárolására … N-1. A következőképpen működik: a fa gyökércsomópontjában vannak benne a 0 tartomány felosztása … N-1-ből a (z) n vödrökbe, amelyek mindegyike nagyjából egy tartományt tart számon \ n egész számok. Ezeket a vödröket ezután mindegyik belsőleg fel van osztva a következő részekre: \ (\n\) vödrök, amelyek mindegyike nagyjából \ (\n\) elemeket tartalmaz. A fa áthaladásához a gyökérből indul, meghatározza, hogy melyik vödörbe tartozik, majd rekurzívan folytatja a megfelelő részfát. A vEB-fa felépítésének módja miatt az O(1) időben meghatározhatjuk, hogy melyik részfába ereszkedjünk le, így az O(log log N) lépések után elérjük a fa alját. Ennek megfelelően a VEB-fa keresése csak időt vesz igénybe O(log log N).

Egy másik példa a Hopcroft-Fortune legközelebbi pontpár algoritmus. Ez az algoritmus megpróbálja megtalálni a 2D pontok gyűjteményének két legközelebbi pontját. Úgy működik, hogy létrehoz egy vödrös rácsot, és elosztja a pontokat ezekbe a vödrökbe. Ha az algoritmus bármely pontján találunk egy vödröt, amelyben több van, mint 6 n pont benne, az algoritmus rekurzívan feldolgozza azt a vödröt. A rekurzió maximális mélysége tehát O (log log n), és a rekurziós fa elemzésével megmutatható, hogy a fa minden rétege O(n) munkát végez. Ezért az algoritmus teljes futási ideje O (n log log n).

O(log n) algoritmusok kis bemeneteken

vannak más algoritmusok, amelyek o(log log n) futási időket érnek el olyan algoritmusok használatával, mint a bináris keresés O(log n) méretű objektumokon. Például az x-fast trie adatstruktúra bináris keresést hajt végre a rétegek felett at magasságfa O(log U), így egyes műveleteinek futási ideje O(log log U). A kapcsolódó y-fast trie megkapja az O(log log U) futási idejének egy részét az O(log U) csomópontok kiegyensúlyozott BST-jének fenntartásával, lehetővé téve az ezekben a fákban végzett keresések időben történő futtatását O(log log U). A tango fa és a kapcsolódó multisplay fa adatstruktúrák elemzéseikben O(log log n) kifejezést kapnak, mert olyan fákat tartanak fenn, amelyek mindegyike O(log n) elemeket tartalmaz.

Egyéb példák

más algoritmusok más módon érik el az O(log log n) futási időt. Az interpolációs keresés arra számított, hogy az O(log log n) futásidejű számot talál egy rendezett tömbben, de az elemzés meglehetősen érintett. Végül az elemzés úgy működik, hogy megmutatja, hogy az iterációk száma megegyezik a számmal k oly módon, hogy n2-k kb 2, amelyre log log n a helyes megoldás. Néhány algoritmus, mint például a Cheriton-Tarjan MST algoritmus, egy komplex, korlátozott optimalizálási probléma megoldásával érkezik o(log log n).

Remélem, ez segít!

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé.