Amarengo

Articles and news

mikä aiheuttaisi algoritmille O (log log n) – kompleksisuuden?

O (log log n) – termejä voi ilmestyä moneen eri paikkaan, mutta tyypillisesti tähän ajoaikaan saapuu kaksi pääreittiä.

kutistuminen neliöjuurella

kuten linkitettyyn kysymykseen annetussa vastauksessa mainittiin, yleinen tapa algoritmille saada aikakompleksisuus O(log n) on, että kyseinen algoritmi toimii leikkaamalla toistuvasti syötteen kokoa jonkin vakiokertoimen verran alaspäin jokaisessa iteraatiossa. Jos näin on, algoritmin on päätyttävä O(log n) – iteraatioiden jälkeen, koska tehtyään o(log n) – jaot vakiolla algoritmin on kutistettava ongelmakoko alas arvoon 0 tai 1. Tämän vuoksi esimerkiksi binäärihaussa on monimutkaisuus O (log n).

mielenkiintoista on, että on olemassa samanlainen tapa pienentää ongelman kokoa, jolla saadaan O-muodon(log log n) juoksuajat. Sen sijaan, että jakamalla panos puoli kunkin kerroksen, mitä tapahtuu, jos otamme neliöjuuri koko kussakin kerroksessa?

otetaan esimerkiksi luku 65 536. Montako kertaa tämä pitää jakaa 2: lla, kunnes päästään 1: een? Jos teemme tämän, saamme

  • 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

tämä prosessi kestää 16 vaihetta, ja se on myös niin, että 65,536 = 216.

mutta jos otamme neliöjuuren jokaisella tasolla, saamme

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

huomaa, että se kestää vain neljä askelta päästä aina alas 2. Mistä tämä johtuu?

ensin intuitiivinen selitys. Kuinka monta numeroa on olemassa numerot n ja √n? Luvussa n on noin log n-numeroa ja noin log (√n) = log (N1/2) = (1/2) log n-numeroa √n. Tämä tarkoittaa sitä, että joka kerta, kun otat neliöjuuren, olet karkeasti puolittaa numeron määrä. Koska voit vain puolittaa määrä k O (log k) kertaa ennen kuin se putoaa alas vakio (sano, 2), tämä tarkoittaa, että voit vain ottaa neliön juuret O(log log n) kertaa ennen kuin olet vähentänyt määrä alas joitakin vakio (sano, 2).

nyt tehdään vähän matematiikkaa, että tästä tulee tiukkaa. Le ’ t kirjoittaa yllä järjestyksessä mitattuna valtuuksia kaksi:

  • √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

huomaa, että seurasimme sekvenssi 216 → 28 → 24 → 22 → 21. Jokaisella iteraatiolla leikkaamme kahden potenssin eksponentin kahtia. Se on mielenkiintoista, koska tämä liittyy takaisin siihen, mitä jo tiedämme – voit vain jakaa luvun k puoliksi O(log k) kertaa ennen kuin se laskee nollaan.

ota siis mikä tahansa luku n ja kirjoita se muotoon n = 2k. Joka kerta, kun otetaan n: n neliöjuuri, puolitetaan eksponentti tässä yhtälössä. Siksi voidaan käyttää vain o (log k) neliöjuuria ennen kuin k laskee 1: een tai alempaan (jolloin n laskee 2: een tai alempaan). Koska n = 2k, tämä tarkoittaa, että k = log2 n, ja siten määrä neliön juuret otetaan on O(log k) = O(log log n). Siksi, jos on algoritmi, joka toimii toistuvasti vähentää ongelman koko, joka on neliöjuuri alkuperäisen ongelman koko, että algoritmi päättyy jälkeen O(log log n) vaiheet.

yksi reaalimaailman esimerkki tästä on van Emde Boas tree (vEB-tree) – tietorakenne. VEB-tree on erikoistunut tietorakenne kokonaislukujen tallentamiseen alueella 0 … N – 1. Se toimii seuraavasti :puun juurisolmussa on √N osoittimia, jotka jakavat alueen 0… N-1 osaksi √n kauhat kullakin tilalla valikoima noin √n kokonaislukua. Nämä kauhat ovat sitten kukin sisäisesti jaettu √ (√n) kauhat, joista jokainen omistaa noin √(√ N) elementtejä. Puun läpi kulkeminen aloitetaan juuresta, määritetään, mihin ämpäriin kuulut, ja jatketaan sitten rekursiivisesti sopivassa alapäässä. VEB-puun rakenteen ansiosta voit määrittää O(1) ajassa, mihin alapuuhun laskeudut, joten O (log log N) – vaiheiden jälkeen pääset puun pohjalle. Niinpä vEB-puun etsinnät vievät aikaa vain O(log log N).

toinen esimerkki on Hopcroft-Fortune lähimmän pisteparin algoritmi. Tämä algoritmi yrittää löytää kaksi lähintä pistettä 2D-pisteiden kokoelmasta. Se toimii luomalla verkkoon ämpäreitä ja jakaa pisteitä niihin ämpäreihin. Jos algoritmin jostakin kohdasta löytyy ämpäri, jossa on enemmän kuin √N pistettä, algoritmi käsittelee ämpärin rekursiivisesti. Rekursion suurin syvyys on siis O(log log n), ja rekursiopuun analyysillä voidaan osoittaa, että jokainen puun kerros tekee o (n) työtä. Siksi algoritmin kokonaisajoaika on O (n log log n).

o(log n) – algoritmit pienillä tuloilla

on olemassa joitakin muita algoritmeja, jotka saavuttavat O(log log n) – suoritusajat käyttämällä algoritmeja, kuten binäärihakua O-kokoisilla olioilla (log n). Esimerkiksi x-fast Tree-tietorakenne suorittaa binäärihaun korkeuspuussa O(log U) olevien kerrosten yli, joten joidenkin sen toimintojen suoritusaika on O(log log U). Aiheeseen liittyvä y-fast trie saa osan O(log log U) – ajonajoistaan ylläpitämällä tasapainoisia O(log U) – solmujen BST: Itä, jolloin hakuja näissä puissa voidaan suorittaa ajassa O (log log U). Tangopuu ja siihen liittyvät multisplay tree-Tietorakenteet päätyvät analyyseissaan O(log log n) – termiin, koska ne ylläpitävät puita, joissa kussakin on o (log n) – kohteita.

muut esimerkit

muut algoritmit saavuttavat runtime O: n (log log n) muilla tavoin. Interpolointi haku on odottanut runtime O (log log n) löytää numero lajiteltu array, mutta analyysi on melko mukana. Lopulta analyysi toimii osoittamalla, että iteraatioiden lukumäärä on yhtä suuri kuin luku k siten, että n2-k ≤ 2, jolle log log n on oikea ratkaisu. Jotkut algoritmit, kuten Cheriton-Tarjan MST-algoritmi, saapuvat ajonaikaan, johon liittyy O (log log n) ratkaisemalla monimutkaisen rajoittuneen optimointiongelman.

Hope this helps!

Vastaa

Sähköpostiosoitettasi ei julkaista.