Amarengo

Articles and news

hvad ville forårsage en algoritme til at have O(log log n) kompleksitet?

o(log log n) vilkår kan dukke op på en række forskellige steder, men der er typisk to hovedruter, der ankommer til denne runtime.

krympning med en kvadratrod

som nævnt i svaret på det linkede spørgsmål er en almindelig måde for en algoritme at have tidskompleksitet O(log n), at algoritmen fungerer ved gentagne gange at skære størrelsen på input ned med en konstant faktor på hver iteration. Hvis dette er tilfældet, skal algoritmen afslutte efter o(log n) iterationer, fordi efter at have udført o(log n) divisioner med en konstant, skal algoritmen krympe problemstørrelsen ned til 0 eller 1. Dette er grunden til, for eksempel, binær søgning har kompleksitet O(log n).

interessant nok er der en lignende måde at krympe ned på størrelsen af et problem, der giver runtimes af formularen O(log log n). I stedet for at dele input i halvdelen ved hvert lag, Hvad sker der, hvis vi tager kvadratroden af størrelsen ved hvert lag?

lad os for eksempel tage nummeret 65.536. Hvor mange gange skal vi dele dette med 2, indtil vi kommer ned til 1? Hvis vi gør det, 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 proces tager 16 trin, og det er også tilfældet, at 65.536 = 216.

men hvis vi tager kvadratroden på hvert niveau, får vi

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

Bemærk, at det kun tager fire trin for at komme helt ned til 2. Hvorfor er det?

først en intuitiv forklaring. Hvor mange cifre er der i tallene n og n? Der er ca. log n-cifre i tallet n, og ca. log (kur n) = log (n1/2) = (1/2) log n-cifre i kur n. Det betyder, at hver gang du tager en kvadratrod, halverer du stort set antallet af cifre i nummeret. Fordi du kun kan halvere en mængde k O(log k) gange, før den falder ned til en konstant (sige 2), betyder det, at du kun kan tage firkantede rødder O(log log n) gange, før du har reduceret antallet ned til nogle konstante (sige 2).

lad os nu lave noget matematik for at gøre dette strengt. Le ‘ TS omskrive ovenstående sekvens i form af beføjelser 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

Bemærk, at vi fulgte sekvensen 216 → 28 → 24 → 22 → 21. På hver iteration skærer vi eksponenten for kraften på to i halvdelen. Det er interessant, fordi dette forbinder tilbage til det, vi allerede ved – du kan kun dele tallet k i halv o(log k) gange, før det falder til nul.

så tag et hvilket som helst tal n og skriv det som n = 2k. Hver gang du tager kvadratroden af n, halverer du eksponenten i denne ligning. Derfor kan der kun anvendes o(log k) firkantede rødder, før k falder til 1 eller lavere (i hvilket tilfælde n falder til 2 eller lavere). Da n = 2K betyder det, at k = log2 n, og derfor er antallet af firkantede rødder taget O(log k) = O(log log n). Derfor, hvis der er algoritme, der fungerer ved gentagne gange at reducere problemet til et underproblem med størrelse, der er kvadratroden af den oprindelige problemstørrelse, afsluttes algoritmen efter o(log log n) trin.

et virkeligt eksempel på dette er van Emde Boas tree (vEB-tree) datastruktur. Et vEB-træ er en specialiseret datastruktur til lagring af heltal i området 0 … N – 1. Det fungerer som følger: træets rodknude har en værdi af n-pointer i den og opdeler området 0 … N-1 ind i kr.n spande, der hver har en række omtrent kr. n heltal. Disse spande er derefter hver internt opdelt i poler (poler n), som hver indeholder omtrent poler (poler n) elementer. For at krydse træet starter du ved roden, bestemmer hvilken spand du tilhører, og fortsæt derefter rekursivt i det relevante undertræ. På grund af den måde, hvorpå vEB-træet er struktureret, kan du bestemme I O(1) tid, hvilket undertræ der skal ned i, og så efter o(log log N) trin når du bunden af træet. Derfor tager opslag i et vEB-træ kun tid O (log log N).

Et andet eksempel er Hopcroft-Fortune nærmeste par punkter algoritme. Denne algoritme forsøger at finde de to nærmeste punkter i en samling af 2D-point. Det virker ved at skabe et gitter af spande og distribuere punkterne i disse spande. Hvis der på et hvilket som helst tidspunkt i algoritmen findes en spand, der har mere end kr.n-punkter i den, behandler algoritmen rekursivt den spand. Den maksimale dybde af rekursionen er derfor O(log log n), og ved hjælp af en analyse af rekursionstræet kan det vises, at hvert lag i træet fungerer O (n). Derfor er den samlede driftstid for algoritmen O (n log log n).

O(log n) algoritmer på små indgange

der er nogle andre algoritmer, der opnår o(log log n) driftstider ved hjælp af algoritmer som binær søgning på objekter af størrelse O(log n). For eksempel udfører den hurtige trie-datastruktur en binær søgning over lagene af ved træ med højde O(log U), så runtime for nogle af dens operationer er O(log log U). Den relaterede y-fast trie får nogle af sine o(log log U) driftstider ved at opretholde afbalancerede BSTs af O(log U) noder hver, så søgninger i disse træer kan køre i tide O (log log U). Tangotræet og relaterede multisplay-trædatastrukturer ender med et o(log log n) udtryk i deres analyser, fordi de opretholder træer, der indeholder O(log n) elementer hver.

andre eksempler

andre algoritmer opnår runtime O(log log n) på andre måder. Interpolationssøgning har forventet runtime O (log log n) for at finde et nummer i et sorteret array, men analysen er ret involveret. I sidste ende fungerer analysen ved at vise, at antallet af iterationer er lig med tallet k, således at n2-k-kur 2, for hvilken log-log n er den rigtige løsning. Nogle algoritmer, som Cheriton-Tarjan MST-algoritmen, ankommer til en runtime, der involverer o(log log n) ved at løse et komplekst begrænset optimeringsproblem.

håber det hjælper!

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.