Amarengo

Articles and news

wat zou ervoor zorgen dat een algoritme o(log log n) complexiteit heeft?

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

krimpend met een vierkantswortel

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

interessant is dat er een vergelijkbare manier is om de omvang van een probleem te verkleinen, waardoor de runtime van de vorm O(log log n) wordt verkregen. In plaats van de invoer in de helft te delen bij elke laag, wat gebeurt er als we de vierkantswortel nemen van de grootte bij elke laag?

bijvoorbeeld, laten we het getal 65,536 nemen. Hoe vaak moeten we dit delen door 2 tot we terug zijn op 1? Als we dit doen, dan 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 = 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

Dit proces duurt 16 stappen, en dat is ook het geval 65536 = 216.

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

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

merk op dat er maar vier stappen nodig zijn om helemaal naar beneden te komen tot 2. Waarom is dit?

eerst een intuïtieve uitleg. Hoeveel cijfers zitten er in de getallen n en √n? Er zijn ongeveer log n cijfers in het getal n, en ongeveer log (√n) = log (n1/2) = (1/2) log n cijfers in √n. Dit betekent dat elke keer dat je een vierkantswortel neemt, je ruwweg het aantal cijfers in het getal halveert. Omdat je slechts een hoeveelheid k o(log k) keer kunt halveren voordat deze daalt tot een constante (zeg, 2), betekent dit dat je alleen vierkantswortels O(log log n) keer kunt nemen voordat je het getal hebt teruggebracht tot een constante (zeg, 2).

nu, laten we wat wiskunde doen om dit rigoureus te maken. Le ‘ TS herschrijft de bovenstaande volgorde in termen van bevoegdheden van twee:

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

merk op dat we de volgorde volgden 216 → 28 → 24 → 22 → 21. Bij elke iteratie snijden we de exponent van de macht van twee in tweeën. Dat is interessant, want dit sluit aan bij wat we al weten – je kunt het getal k alleen delen in de helft O (log k) keer voordat het naar nul daalt.

neem een willekeurig getal n en schrijf het als n = 2k. 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 aangebracht voordat k daalt tot 1 of lager (in welk geval n daalt tot 2 of lager). Aangezien n = 2k, betekent dit dat k = log2 n, en dus het aantal genomen vierkantswortels is O (log k) = O(log log n). Daarom, als er algoritme dat werkt door het probleem herhaaldelijk te verminderen tot een subprobleem van grootte dat is de vierkantswortel van de oorspronkelijke probleemgrootte, dat algoritme zal eindigen na o(log log n) stappen.

een echt voorbeeld hiervan is de van Emde boas tree (vEB-tree) datastructuur. 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-wijzers erin, waarbij het bereik 0 wordt gedeeld … N-1 in √n emmers die elk een bereik van ruwweg √n gehele getallen houden. Deze emmers worden dan elk intern onderverdeeld in √ (√N) emmers, die elk ongeveer √(√ n) elementen bevat. Om de boom te doorkruisen, begin je bij de root, bepaal je tot welke emmer je behoort en ga je recursief verder in de betreffende subboom. Door de structuur van de vEB-boom kun je in o(1) tijd bepalen in welke subboom je afdaalt, en zo kom je na o(log log n) stappen bij de bodem van de boom. Dienovereenkomstig, lookups in een vEB-boom nemen tijd alleen O (log log n).

een ander voorbeeld is het Hopcroft-Fortune closest pair of points algoritme. Dit algoritme probeert de twee dichtstbijzijnde punten te vinden in een verzameling van 2D-punten. Het werkt door het creëren van een raster van emmers en het verdelen van de punten in die emmers. Als op enig punt in het algoritme een emmer wordt gevonden die meer dan √N punten erin heeft, verwerkt het algoritme die emmer recursief. De maximale diepte van de recursie is daarom O (log log n), en met behulp van een analyse van de recursie boom kan worden aangetoond dat elke laag in de boom werkt O(n). Daarom is de totale runtime 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 bereiken door algoritmen te gebruiken zoals binaire zoekopdrachten op objecten van grootte O (log n). Bijvoorbeeld, de x-fast trie data structuur voert een binaire zoekopdracht over de lagen van AT tree of height O (log U), dus de runtime voor sommige van zijn operaties zijn O(log log u). De verwante y-fast trie krijgt een aantal van zijn o(log log U) runtimes door het handhaven van evenwichtige BST ‘ s van o(log U) nodes elk, waardoor zoekopdrachten in die bomen om te draaien in de tijd O (log log u). De tango tree en gerelateerde multisplay tree data structuren eindigen met een O(log log n) term in hun analyses omdat ze bomen onderhouden die elk o (log n) items bevatten.

andere voorbeelden

andere algoritmen bereiken runtime O (log log n) op andere manieren. Interpolatie zoeken heeft verwacht runtime O (log log n) om een nummer te vinden in een gesorteerde array, maar de analyse is vrij betrokken. Uiteindelijk werkt de analyse door aan te tonen dat het aantal iteraties gelijk is aan het getal k zodat n2-k ≤ 2, waarvoor log log n de juiste oplossing is. Sommige algoritmen, zoals de Cheriton-Tarjan MST algoritme, komen tot een runtime waarbij o(log log n) door het oplossen van een complex beperkt optimalisatie probleem.

hoop dat dit helpt!

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.