Amarengo

Articles and news

ce ar determina un algoritm să aibă o (log log n) complexitate?

termenii O(log log n) pot apărea într-o varietate de locuri diferite, dar există de obicei două rute principale care vor ajunge în acest timp de rulare.

micșorarea cu o rădăcină pătrată

după cum se menționează în răspunsul la întrebarea legată, o modalitate obișnuită pentru ca un algoritm să aibă complexitatea timpului O(log n) este ca acel algoritm să funcționeze prin reducerea repetată a dimensiunii intrării cu un factor constant pe fiecare iterație. Dacă acesta este cazul, algoritmul trebuie să se termine după o(log n) iterații, deoarece după efectuarea diviziunilor O(log n) cu o constantă, algoritmul trebuie să micșoreze dimensiunea problemei până la 0 sau 1. Acesta este motivul pentru care, de exemplu, căutarea binară are complexitate O(log n).

interesant, există un mod similar de scădere în jos dimensiunea unei probleme care randamentele runtimes de forma o(log log n). În loc Să împărțim intrarea în jumătate la fiecare strat, ce se întâmplă dacă luăm rădăcina pătrată a dimensiunii la fiecare strat?

de exemplu, să luăm numărul 65.536. De câte ori trebuie să împărțim acest lucru la 2 până când ajungem la 1? Dacă facem asta, obținem

  • 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

acest proces are 16 pași, și este, de asemenea, cazul în care 65,536 = 216.

dar, dacă luăm rădăcina pătrată la fiecare nivel, obținem

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

observați că este nevoie de doar patru pași pentru a obține tot drumul până la 2. De ce este asta?

în primul rând, o explicație intuitivă. Câte cifre există în numerele n și n-uri? Există aproximativ log n cifre în numărul n, și aproximativ log (hectolitru n) = log (n1/2) = (1/2) log n cifre în hectolitru n. Aceasta înseamnă că, de fiecare dată când luați o rădăcină pătrată, reduceți aproximativ la jumătate numărul de cifre din număr. Deoarece puteți reduce doar la jumătate o cantitate k o (log k) ori înainte de a scădea la o constantă (să zicem, 2), Aceasta înseamnă că puteți lua doar rădăcini pătrate o(log log n) ori înainte de a reduce numărul la o constantă (să zicem, 2).

acum, să facem niște calcule pentru a face acest lucru riguros. Le ‘ TS rescrie secvența de mai sus în termeni de puteri de două:

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

observați că am urmat secvența 216 → 28 → 24 → 22 → 21. La fiecare iterație, am tăiat exponentul puterii a două în jumătate. Acest lucru este interesant, deoarece acest lucru se conectează înapoi la ceea ce știm deja – puteți împărți numărul k în jumătate O(log k) ori înainte de a scădea la zero.

deci, ia orice număr n și scrie-l ca n = 2K. De fiecare dată când luați rădăcina pătrată a lui n, înjumătățiți exponentul din această ecuație. Prin urmare, pot exista doar rădăcini pătrate o(log k) aplicate înainte ca k să scadă la 1 sau mai jos (caz în care n scade la 2 sau mai jos). Deoarece n = 2K, aceasta înseamnă că k = log2 n și, prin urmare, numărul de rădăcini pătrate luate este O(log k) = o(log log n). Prin urmare, dacă există algoritm care funcționează prin reducerea repetată a problemei la o subproblemă de dimensiune care este rădăcina pătrată a dimensiunii problemei originale, acel algoritm se va termina după pașii O(log log n).

Un exemplu real în acest sens este structura de date van Emde boas tree (vEB-tree). Un arbore vEB este o structură de date specializată pentru stocarea numerelor întregi în intervalul 0 … N-1. Funcționează după cum urmează: nodul rădăcină al arborelui are în el indicii de n-uri, împărțind intervalul 0 … N – 1 în găleți de n-uri de n-uri, fiecare conținând o gamă de numere întregi aproximativ de n-uri de-a dreptul de-a-n-uri. Aceste găleți sunt apoi fiecare subdivizate intern în găleți de la sec. Pentru a traversa copacul, începeți de la rădăcină, determinați ce găleată aparțineți, apoi continuați recursiv în subarborele corespunzător. Datorită modului în care este structurat arborele vEB, puteți determina în O(1) timp în care subarborele să coboare și astfel după pașii O (log log N) veți ajunge în partea de jos a arborelui. În consecință, căutări într-un vEB-copac ia timp doar O(log log N).

Un alt exemplu este Hopcroft-Fortune cea mai apropiată pereche de puncte algoritm. Acest algoritm încearcă să găsească cele mai apropiate două puncte într-o colecție de puncte 2D. Funcționează prin crearea unei rețele de găleți și distribuirea punctelor în acele găleți. Dacă în orice moment al algoritmului se găsește o găleată care are mai mult de centimetrul n puncte în ea, algoritmul procesează recursiv acea găleată. Prin urmare, adâncimea maximă a recursivității este o(log log n) și folosind o analiză a arborelui de recursivitate se poate arăta că fiecare strat din copac funcționează O(n). Prin urmare, timpul total de rulare al algoritmului este O(n log log n).

algoritmi O(log n) pe intrări mici

există și alți algoritmi care realizează runtime O(log log n) folosind algoritmi precum căutarea binară pe obiecte de dimensiune O(log n). De exemplu, structura de date x-fast Trie efectuează o căutare binară peste straturile arborelui at de înălțime O(log U), astfel încât timpul de rulare pentru unele dintre operațiunile sale este O(log log U). Procesul y-rapid legat primește o parte din timpul său de rulare O(log log U) prin menținerea BST-urilor echilibrate ale nodurilor O(log U) fiecare, permițând căutărilor în acei copaci să ruleze în timp O(log log U). Arborele tango și structurile de date asociate arborelui multisplay se termină cu un termen O(log log n) în analizele lor, deoarece mențin copaci care conțin elemente o(log n) fiecare.

alte exemple

alți algoritmi realizează runtime O(log log n) în alte moduri. Căutare interpolare a așteptat runtime o (log log n) pentru a găsi un număr într-o matrice sortate, dar analiza este destul de implicat. În cele din urmă, analiza funcționează arătând că numărul de iterații este egal cu numărul k, astfel încât N2-k 2, pentru care log log n este soluția corectă. Unii algoritmi, cum ar fi algoritmul Cheriton-Tarjan MST, ajung la un timp de rulare care implică O(log log n) prin rezolvarea unei probleme complexe de optimizare constrânsă.

Sper că acest lucru vă ajută!

Lasă un răspuns

Adresa ta de email nu va fi publicată.