Amarengo

Articles and news

vad skulle orsaka att en algoritm har O (log log n) komplexitet?

o(log log n) termer kan dyka upp på en mängd olika platser, men det finns vanligtvis två huvudvägar som kommer fram till denna körtid.

krymper med en kvadratrot

som nämnts i svaret på den länkade frågan är ett vanligt sätt för en algoritm att ha tidskomplexitet O(log n) för att algoritmen ska fungera genom att upprepade gånger minska storleken på ingången med någon konstant faktor på varje iteration. Om så är fallet måste algoritmen avslutas efter o(log n) iterationer, för efter att ha gjort o (log n) divisioner med en konstant måste algoritmen krympa problemstorleken ner till 0 eller 1. Det är därför, till exempel, binär sökning har komplexitet O(log n).

intressant är att det finns ett liknande sätt att krympa ner storleken på ett problem som ger körtider av formen O(log log n). Istället för att dela in ingången i hälften vid varje lager, vad händer om vi tar kvadratroten av storleken vid varje lager?

till exempel, låt oss ta numret 65,536. Hur många gånger måste vi dela detta med 2 tills vi kommer ner till 1? Om 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

denna process tar 16 steg, och det är också så att 65,536 = 216.

men om vi tar kvadratroten på varje nivå får vi

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

Observera att det bara tar fyra steg för att komma hela vägen ner till 2. Varför är det här?

först en intuitiv förklaring. Hur många siffror finns det i numren n och SR n? Det finns ungefär log n siffror i numret n, och ungefär log (0 n) = log (n1/2) = (1/2) log n siffror i 2 n. Det betyder att varje gång du tar en kvadratrot halverar du ungefär antalet siffror i numret. Eftersom du bara kan halvera en mängd k O (log k) gånger innan den sjunker ner till en konstant(säg 2) betyder det att du bara kan ta kvadratrötter O (log log n) gånger innan du har minskat antalet till någon konstant (säg 2).

nu, låt oss göra lite matte för att göra detta rigorösa. Le ’ TS skriva om ovanstående sekvens i termer av befogenheter två:

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

Observera att vi följde sekvensen 216 → 28 → 24 → 22 → 21. Vid varje iteration skär vi exponenten för kraften i två i hälften. Det är intressant, för det här ansluter till det vi redan vet – du kan bara dela numret k i halva o(log k) gånger innan det sjunker till noll.

så ta valfritt nummer n och skriv det som n = 2K. Varje gång du tar kvadratroten av n halverar du exponenten i denna ekvation. Därför kan det bara finnas o (log k) kvadratrötter applicerade innan k sjunker till 1 eller lägre (i vilket fall n sjunker till 2 eller lägre). Eftersom n = 2K betyder det att k = log2 n, och därför är antalet kvadratrötter som tas O(log k) = O(log log n). Därför, om det finns algoritm som fungerar genom att upprepade gånger reducera problemet till ett delproblem av storlek som är kvadratroten av den ursprungliga problemstorleken, kommer den algoritmen att avslutas efter o(log log n) steg.

Ett verkligt exempel på detta är datastrukturen van Emde Boas tree (vEB-tree). Ett vEB-träd är en specialiserad datastruktur för lagring av heltal i intervallet 0 … N – 1. Det fungerar som följer: trädets rotnod har en pekare i det, vilket delar upp intervallet 0 … N-1 in i chubbi n hinkar var och en håller en rad av ungefär chubbi N heltal. Dessa hinkar är sedan var och en internt indelad i hinkar av typen 2bn (NBN), som var och en rymmer ungefär tvåbn (NBN) element. För att korsa trädet börjar du vid roten, bestämmer vilken hink du tillhör och fortsätter sedan rekursivt i lämpligt underträd. På grund av hur vEB-trädet är strukturerat kan du bestämma I O(1) tid vilket underträd som ska gå ner i, och så efter o(log log N) steg kommer du att nå botten av trädet. Följaktligen tar uppslag i ett vEB-träd endast tid O (log log N).

Ett annat exempel är Hopcroft-Fortune närmaste par punkter algoritm. Denna algoritm försöker hitta de två närmaste punkterna i en samling 2D-poäng. Det fungerar genom att skapa ett rutnät av hinkar och fördela punkterna i dessa hinkar. Om det vid någon punkt i algoritmen finns en hink som har mer än 2bn-poäng i den, bearbetar algoritmen rekursivt den hinken. Det maximala djupet för rekursionen är därför O (log log n), och med hjälp av en analys av rekursionsträdet kan det visas att varje lager i trädet fungerar O(n). Därför är algoritmens totala körtid O (n log log n).

o(log n) algoritmer på små ingångar

det finns några andra algoritmer som uppnår o(log log n) runtimes genom att använda algoritmer som binär sökning på objekt av storlek O(log n). Till exempel utför X-fast trie-datastrukturen en binär sökning över lagren av vid träd av höjd O(log U), så körtiden för vissa av dess operationer är O(log log U). Den relaterade y-fast trie får några av sina o(log log U) runtimes genom att upprätthålla balanserade BST av O(log U) noder vardera, vilket gör att sökningar i dessa träd kan köras i tid O (log log U). Tangoträdet och relaterade multispelsträddatastrukturer slutar med en O(log log n) term i sina analyser eftersom de upprätthåller träd som innehåller o (log n) objekt vardera.

andra exempel

andra algoritmer uppnår runtime O(log log n) på andra sätt. Interpolationssökning har förväntat runtime O (log log n) för att hitta ett tal i en sorterad array, men analysen är ganska involverad. I slutändan fungerar analysen genom att visa att antalet iterationer är lika med antalet k så att N2-k 2, för vilken log log n är den rätta lösningen. Vissa algoritmer, som Cheriton-Tarjan mst-algoritmen, anländer till en körtid som involverar O(log log n) genom att lösa ett komplext begränsat optimeringsproblem.

hoppas detta hjälper!

Lämna ett svar

Din e-postadress kommer inte publiceras.