Amarengo

Articles and news

Hva vil føre til at en algoritme har o (log log n) kompleksitet?

o (log log n) vilkår kan dukke opp på en rekke forskjellige steder, men det er vanligvis to hovedruter som kommer til denne kjøretiden.

Krymper Med En Kvadratrot

som nevnt i svaret på det koblede spørsmålet, er en vanlig måte for en algoritme å ha tidskompleksitet O(log n) for at algoritmen skal fungere ved å gjentatte ganger kutte størrelsen på inngangen ned med en konstant faktor på hver iterasjon. Hvis dette er tilfelle, må algoritmen avslutte Etter O (log n) iterasjoner, fordi etter å ha Gjort O(log n) divisjoner med en konstant, må algoritmen krympe problemstørrelsen ned til 0 eller 1. Det er derfor, for eksempel, binært søk har kompleksitet O (log n).

Interessant er det en lignende måte å krympe ned størrelsen på et problem som gir kjøretider av skjemaet O (log log n). I stedet for å dele inngangen i halv på hvert lag, hva skjer hvis vi tar kvadratroten av størrelsen på hvert lag?

la oss for eksempel ta tallet 65 536. Hvor mange ganger må vi dele dette med 2 til vi kommer ned til 1? Hvis vi gjør dette, får vi

  • 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

Denne prosessen tar 16 trinn, og det er også tilfelle at 65,536 = 216.

Men hvis vi tar kvadratroten på hvert nivå, får vi

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

Legg merke til at det bare tar fire trinn for å komme helt ned til 2. Hvorfor er dette?

Først en intuitiv forklaring. Hvor mange sifre er det i tallene n og √n? Det er omtrent logg n-sifre i tallet n, og omtrent logg (√n) = logg (n1/2) = (1/2) logg n-sifre i √n. Dette betyr at hver gang du tar en kvadratrot, halverer du omtrent antall siffer i nummeret. Fordi du bare kan halvere en mengde k O (log k) ganger før den faller ned til en konstant (si 2), betyr dette at du bare kan ta kvadratrøtter O (log log n) ganger før du har redusert tallet ned til noen konstant (si 2).

Nå, la oss gjøre litt matte for å gjøre dette strenge. Le ‘ ts omskrive ovennevnte sekvens i form av krefter to:

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

Legg Merke til at vi fulgte sekvensen 216 → 28 → 24 → 22 → 21. På hver iterasjon kutter vi eksponenten av kraften til to i halvparten. Det er interessant, fordi dette kobles tilbake til det vi allerede vet-du kan bare dele tallet k i halv O (log k) ganger før det faller til null.

så ta et hvilket som helst tall n og skriv det som n = 2k. Hver gang du tar kvadratroten av n, halverer du eksponenten i denne ligningen. Derfor kan Det bare Brukes o(log k) kvadratrøtter før k faller til 1 eller lavere (i så fall faller n til 2 eller lavere). Siden n = 2k betyr dette at k = log2 n, og derfor er antall kvadratrøtter tatt O (log k) = O (log log n). Derfor, hvis det er algoritme som fungerer ved gjentatte ganger å redusere problemet til et delproblem av størrelse som er kvadratroten av den opprinnelige problemstørrelsen, avsluttes algoritmen etter o (log log n) trinn.

et eksempel på dette er datastrukturen van Emde Boas tree (vEB-tree). Et vEB-tre er en spesialisert datastruktur for lagring av heltall i området 0 … N – 1. Det fungerer som følger: rotnoden til treet har √N pekere i den, og deler området 0 … N-1 til √N-skuffer som hver har et utvalg av omtrent √N heltall. Disse skuffene blir så internt oppdelt i √(√ N) – bøtter, som hver har omtrent √(√ N) elementer. For å krysse treet, starter du ved roten, bestemmer hvilken bøtte du tilhører, og fortsetter rekursivt i riktig undertre. På grunn av måten vEB-treet er strukturert, kan Du bestemme I O (1) tid som subtre å stige inn, og så Etter O (log log N) trinn vil du nå bunnen av treet. Følgelig tar oppslag i et vEB-tre bare Tid O (log log N).

Et annet eksempel Er Hopcroft-Fortune closest pair of points-algoritmen. Denne algoritmen forsøker å finne de to nærmeste punktene i en samling AV 2D-poeng. Det fungerer ved å lage et rutenett av bøtter og distribuere punktene i disse bøtter. Hvis det på noe tidspunkt i algoritmen er funnet en bøtte som har mer Enn √N poeng i den, behandler algoritmen rekursivt den bøtte. Maksimal dybde på rekursjonen Er Derfor O (log log n), og ved hjelp av en analyse av rekursjonstreet kan det vises at hvert lag i treet Gjør O(n) arbeid. Derfor er den totale kjøretiden Til algoritmen O (n log log n).

O (log n) Algoritmer På Små Innganger

Det er noen andre algoritmer som oppnår O (log log n) kjøretider ved å bruke algoritmer som binært søk på objekter Av Størrelse O (log n). For eksempel utfører x-fast trie datastrukturen et binært søk over lagene av at tree of height O(log U), så kjøretiden for noen av operasjonene Er O (log log U). Den relaterte y-fast trie får noen Av Sine O (log log U) kjøretider ved å opprettholde balansert BSTs Av O (log U) noder hver, slik at søk i disse trærne for å kjøre i tid O (log log U). Tango treet og relaterte multisplay tre datastrukturer ende opp Med En O (log log n) sikt i sine analyser fordi de opprettholder trær som inneholder O (log n) elementer hver.

Andre Eksempler

Andre algoritmer oppnår runtime O (log log n) på andre måter. Interpolasjonssøk har forventet runtime O (log log n) for å finne et tall i en sortert array, men analysen er ganske involvert. Til syvende og sist fungerer analysen ved å vise at antall iterasjoner er lik tallet k slik at n2-k ≤ 2, for hvilken logglogg n er den riktige løsningen. Noen algoritmer, som Cheriton-Tarjan mst-algoritmen, kommer til en kjøretid som involverer O (log log n) ved å løse et komplekst begrenset optimaliseringsproblem.

Håper dette hjelper!

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.