Waarom zou een algoritme O(log log n) complexiteit hebben?

Deze eerdere vraagbehandelt enkele van de factoren die ervoor kunnen zorgen dat een algoritme O(log n) complexiteit heeft.

Waarom zou een algoritme tijdcomplexiteit O(log log n) hebben?

Antwoord 1, autoriteit 100%

O(log log n)-termen kunnen op verschillende plaatsen verschijnen, maar er zijn meestal twee hoofdroutes die tijdens deze runtime aankomen.

Krimpen met een vierkantswortel

Zoals vermeld in het antwoord op de gekoppelde vraag, is een gebruikelijke manier voor een algoritme om tijdcomplexiteit O(log n) te hebben, dat dat algoritme werkt door herhaaldelijk de grootte van de invoer te verkleinen met een constante factor bij elke iteratie . Als dit het geval is, moet het algoritme eindigen na O(log n) iteraties, want na het doen van O(log n) delingen door een constante, moet het algoritme de probleemgrootte verkleinen tot 0 of 1. Dit is de reden waarom bijvoorbeeld , binair zoeken heeft complexiteit O(log n).

Interessant is dat er een vergelijkbare manier is om de omvang van een probleem te verkleinen dat runtimes oplevert van de vorm O(log log n). Wat gebeurt er als we in elke laag de vierkantswortel van de groottenemen in plaats van de invoer in elke laag in tweeën te delen?

Laten we bijvoorbeeld het getal 65.536 nemen. Hoe vaak moeten we dit door 2 delen totdat we op 1 uitkomen? Als we dit doen, krijgen we

• 65.536 / 2 = 32.768
• 32.768 / 2 = 16.384
• 16.384 / 2 = 8.192
• 8.192 / 2 = 4.096
• 4,096 / 2 = 2048
• 2.048 / 2 = 1.024
• 1024 / 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

Dit proces duurt 16 stappen, en het is ook het geval dat 65.536 = 2 ^{16 .}

Maar als we de vierkantswortel op elk niveau nemen, krijgen we

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

Merk op dat het maar vier stappen duurt om helemaal tot 2. Waarom is dit?

Ten eerste, een intuïtieve verklaring. Hoeveel cijfers zijn er in de cijfers n en √n? Er zijn ongeveer log N-cijfers in het nummer n en ongeveer log (√n) = log (n ^{1/2 ) = (1/2) log N cijfers in √n. Dit betekent dat elke keer dat u een vierkantswortel inneemt, u het aantal cijfers in het nummer ruwt. Omdat je alleen een hoeveelheid K O (log k) tijden kunt halveren voordat het daalt naar een constante (zeg, 2), betekent dit dat je alleen maar vierkante wortels o (log log n) tijden kunt maken voordat je het nummer naar beneden hebt gereduceerd naar een constante (zeg, 2).}

Nu, laten we wat wiskunde doen om dit rigoureus te maken. Le’ts herschrijven de bovenstaande volgorde in termen van bevoegdheden van twee:

• √65.536 = √2 ^{16 = (2 16 ) 1/2 = 2 8 = 256}
• √256 = √2 ^{8 = (2 8 ) 1/2 = 2 4 = 16}
• √16 = √2 ^{4 = (2 4 ) 1/2 = 2 2 = 4}
• √4 = √2 ^{2 = (2 2 ) 1/2 = 2 1 = 2}

Merk op dat we de volgorde hebben gevolgd 2 ^{16 → 2 8 → 2 4 → 2 2 → 2 1 . Op elke iteratie snijden we de exponent van de kracht van twee in de helft. Dat is interessant, want dit maakt terug naar wat we al kennen – je kunt alleen het nummer K in de helft O (log K) -tijden verdelen voordat het naar nul daalt.}

Neem dus een willekeurig getal n en schrijf het als n = 2^k. Elke keer dat je de vierkantswortel van n neemt, halveer je de exponent in deze vergelijking. Daarom kunnen er alleen O(log k) vierkantswortels worden toegepast voordat k daalt tot 1 of lager (in welk geval n daalt tot 2 of lager). Aangezien n = 2^k, betekent dit dat k = log₂n, en daarom is het aantal genomen vierkantswortels O(log k) = O(log log n) . Daarom, als er een algoritme is dat werkt door het probleem herhaaldelijk te reduceren tot een subprobleem van grootte dat de vierkantswortel is van de oorspronkelijke probleemgrootte, zal dat algoritme eindigen na O(log log n) stappen.

Een praktijkvoorbeeld hiervan is de van Emde Boas-boom(vEB-boom) data structuur. Een vEB-tree is een gespecialiseerde datastructuur voor het opslaan van gehele getallen in het bereik 0 … N – 1. Het werkt als volgt: het wortelknooppunt van de boom heeft √N-aanwijzers erin, waardoor het bereik 0 … N – wordt gesplitst. 1 in √N emmers die elk een bereik van ongeveer √N gehele getallen bevatten. Deze emmers worden vervolgens elk intern onderverdeeld in √(√ N) emmers, die elk ongeveer √(√ N) elementen bevatten. Om de boom te doorkruisen, begin je bij de wortel, bepaal je tot welke bucket je behoort en ga je recursief verder in de juiste subboom. Door de manier waarop de vEB-tree is gestructureerd, kun je in O(1) tijd bepalen in welke subtree je moet afdalen, en dus na O(log log N) stappen zul je de onderkant van de tree bereiken. Het opzoeken in een vEB-tree kost dus slechts tijd O(log log N).

Nog een voorbeeld is de Hopcroft-Fortune dichtstbijzijnde paar puntenalgoritme . Dit algoritme probeert de twee dichtstbijzijnde punten in een verzameling van 2D-punten te vinden. Het werkt door een raster emmers te maken en de punten in die emmers te verdelen. Als op enig moment in het algoritme een emmer wordt gevonden die er meer dan √n-punten in heeft, verwerkt het algoritme die emmer recursief is. De maximale diepte van de recursie is daarom O (log log n) en het gebruik van een analyse van de recursietboom kan worden aangetoond dat elke laag in de boom o (n) werk doet. Daarom is de totale looptijd van het algoritme O (n log log n).

O (log n) algoritmen op kleine ingangen

Er zijn enkele andere algoritmen die o (log log n) runtimes behalen door algoritmen zoals binaire zoekopdracht te gebruiken op objecten van maat O (log n). Bijvoorbeeld, de x-fast trie gegevensstructuur voert een binaire zoekopdracht uit over de lagen van AT Boom van Hoogte O (log u), dus de runtime voor sommige van zijn operaties is O (log log u). De gerelateerde y-fast trie krijgt een deel van zijn O (log log u) looptijden door te handhaven Balanced BSTS OF O (log U) knooppunten elk, waarmee zoekopdrachten in die bomen kunnen worden uitgevoerd in de tijd O (log log u). De tango boom en gerelateerd Multisplay tree gegevensstructuren eindigen met een O (log log n) term in hun analyses omdat ze bomen onderhouden die o (log n) items onderhouden elk.

Andere voorbeelden

Andere algoritmen behalen op andere manieren runtime o (log log n). interpolatie zoeken heeft runtime o (log log n) verwacht om een ​​getal in een gesorteerde array te vinden, maar De analyse is redelijk betrokken. Uiteindelijk werkt de analyse door te laten zien dat het aantal iteraties gelijk is aan het aantal k zodanig dat N ^{2 -K ≤ 2, waarvoor lognog N de juiste oplossing is . Sommige algoritmen, zoals de Cheriton-Tarjan MST-algoritme , aankomen op een runtime met O (log log n) door een complex beperkt optimalisatieprobleem op te lossen.}

Ik hoop dat dit helpt!

Antwoord 2

One Way to Factor van O (log log n) in tijdcomplexiteit is door divisie zoals dingen die in het andere antwoord worden uitgelegd, maar er is een andere manier om deze factor te zien, wanneer we tussen de tijd en Ruimte / tijd en benadering / tijd en hardheid / … van algoritmen en we hebben een kunstmatige iteratie op ons algoritme.

SSSP (SSSP (Single Source Shortest Path) heeft een O (n) algoritme op Planaire grafieken, maar voor dat gecompliceerde algoritme was er een veel eenvoudiger algoritme (maar nog steeds nogal hard) met looptijd o (n log log n ), de basis van het algoritme is als volgt (gewoon een zeer ruwe beschrijving en ik zou aanbieden om dit deel te begrijpen en het andere deel van het antwoord te lezen):

1. Verdeel grafiek in de delen van grootte O (log n / (log log n)) met enige beperking.
2. Stel dat elk van genoemde onderdeel knooppunt is in de nieuwe grafiek G ‘en vervolgens SSP voor G’ in Time O (| g ‘| * log | g’ |) == & GT; hier omdat | g ‘| = O (| g | * log log n / log n) We kunnen de (log log n) factor bekijken.
3. Bereken SSSP voor elk deel: nogmaals omdat we een O(|G’|) deel hebben en we kunnen SSSP voor alle delen in de tijd berekenen |n/logn| * |log n/log logn * log (logn /log log n).
4. gewichten bijwerken, dit kan in O(n).
   voor meer details deze college-aantekeningenzijn goed.

Maar mijn punt is, hier kiezen we de verdeling van grootte O(log n/(log log n)). Als we andere divisies kiezen, zoals O(log n/ (log log n)^2) die mogelijk sneller werkt en een ander resultaat oplevert. Ik bedoel, in veel gevallen (zoals in benaderingsalgoritmen of gerandomiseerde algoritmen, of algoritmen zoals SSSP zoals hierboven), wanneer we iets herhalen (subproblemen, mogelijke oplossingen, …), kiezen we het aantal iteraties dat overeenkomt met de handel van dat we hebben (tijd/ruimte/complexiteit van algoritme/constante factor van het algoritme,…). Dus misschien zien we ingewikkelder dingen dan “log log n” in echt werkende algoritmen.