Amarengo

Articles and news

Cosa causerebbe la complessità di un algoritmo O(log log n)?

O(log log n) i termini possono apparire in una varietà di luoghi diversi, ma in genere ci sono due percorsi principali che arriveranno a questo runtime.

Restringimento di una radice quadrata

Come menzionato nella risposta alla domanda collegata, un modo comune per un algoritmo di avere complessità temporale O(log n) è che l’algoritmo funzioni tagliando ripetutamente la dimensione dell’input di qualche fattore costante su ogni iterazione. In questo caso, l’algoritmo deve terminare dopo iterazioni O(log n), perché dopo aver eseguito le divisioni O(log n) di una costante, l’algoritmo deve ridurre la dimensione del problema a 0 o 1. Questo è il motivo per cui, ad esempio, la ricerca binaria ha complessità O(log n).

È interessante notare che esiste un modo simile di ridurre le dimensioni di un problema che produce runtime del modulo O(log log n). Invece di dividere l’input a metà in ogni livello, cosa succede se prendiamo la radice quadrata della dimensione in ogni livello?

Ad esempio, prendiamo il numero 65,536. Quante volte dobbiamo dividere questo per 2 fino ad arrivare a 1? Se facciamo questo, si ottiene

  • 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

Questo processo prende 16 punti, ed è anche il caso che 65.536 = 216.

Ma, se prendiamo la radice quadrata ad ogni livello, otteniamo

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

Si noti che ci vogliono solo quattro passi per arrivare fino a 2. Perché è questo?

In primo luogo, una spiegazione intuitiva. Quante cifre ci sono nei numeri n e √n? Ci sono approssimativamente log n cifre nel numero n, e approssimativamente log (√n) = log (n1/2) = (1/2) log n cifre in √n. Ciò significa che, ogni volta che si prende una radice quadrata, si sta circa dimezzando il numero di cifre nel numero. Poiché puoi solo dimezzare una quantità k O (log k) volte prima che scenda a una costante(diciamo, 2), questo significa che puoi solo prendere radici quadrate O (log log n) volte prima di aver ridotto il numero a qualche costante (diciamo, 2).

Ora, facciamo un po ‘ di matematica per rendere questo rigoroso. Le’ts riscrivere la sequenza di cui sopra in termini di potenze di due:

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

si Noti che abbiamo seguito la sequenza 216 → 28 → 24 → 22 → 21. Su ogni iterazione, tagliamo l’esponente della potenza di due a metà. Questo è interessante, perché questo si collega a ciò che già sappiamo – puoi solo dividere il numero k a metà O(log k) volte prima che scenda a zero.

Quindi prendi qualsiasi numero n e scrivilo come n = 2k. Ogni volta che prendi la radice quadrata di n, dimezzi l’esponente in questa equazione. Pertanto, possono esserci solo radici quadrate O (log k) applicate prima che k scenda a 1 o inferiore (nel qual caso n scenda a 2 o inferiore). Poiché n = 2k, questo significa che k = log2 n, e quindi il numero di radici quadrate prese è O(log k) = O (log log n). Pertanto, se esiste un algoritmo che funziona riducendo ripetutamente il problema a un sottoproblema di dimensioni che è la radice quadrata della dimensione del problema originale, tale algoritmo terminerà dopo i passaggi O(log log n).

Un esempio reale di questo è la struttura dati van Emde Boas tree (Veb-tree). Un VEB-tree è una struttura dati specializzata per la memorizzazione di numeri interi nell’intervallo 0 … N-1. Funziona come segue: il nodo radice dell’albero ha √N puntatori in esso, dividendo l’intervallo 0 … N-1 in √N secchi ciascuno contenente un intervallo di circa √N interi. Questi bucket sono quindi suddivisi internamente in bucket √ (√ N), ognuno dei quali contiene approssimativamente elementi √(√ N). Per attraversare l’albero, si inizia alla radice, si determina a quale bucket si appartiene, quindi si continua ricorsivamente nella sottoalbero appropriata. A causa del modo in cui l’albero vEB è strutturato, è possibile determinare in O(1) tempo in quale sottoalbero scendere, e quindi dopo O(log log N) passi si raggiungerà il fondo dell’albero. Di conseguenza, le ricerche in un VEB-tree richiedono tempo solo O (log log N).

Un altro esempio è l’algoritmo della coppia di punti più vicina a Hopcroft-Fortune. Questo algoritmo tenta di trovare i due punti più vicini in una raccolta di punti 2D. Funziona creando una griglia di bucket e distribuendo i punti in quei bucket. Se in qualsiasi punto dell’algoritmo viene trovato un bucket che ha più di √N punti in esso, l’algoritmo elabora ricorsivamente quel bucket. La profondità massima della ricorsione è quindi O (log log n), e usando un’analisi dell’albero di ricorsione si può dimostrare che ogni livello nell’albero funziona O(n). Pertanto, il runtime totale dell’algoritmo è O(n log log n).

Algoritmi O(log n) su piccoli input

Esistono altri algoritmi che raggiungono runtime O(log log n) utilizzando algoritmi come la ricerca binaria su oggetti di dimensioni O(log n). Ad esempio, la struttura dati trie x-fast esegue una ricerca binaria sui livelli dell’albero at di altezza O(log U), quindi il runtime per alcune delle sue operazioni è O(log log U). Il relativo trie y-fast ottiene alcuni dei suoi runtime O(log log U) mantenendo BST bilanciati di nodi O(log U) ciascuno, consentendo alle ricerche in quegli alberi di funzionare nel tempo O (log log U). L’albero di tango e le relative strutture di dati ad albero multisplay finiscono con un termine O(log log n) nelle loro analisi perché mantengono alberi che contengono elementi O (log n) ciascuno.

Altri esempi

Altri algoritmi raggiungono runtime O(log log n) in altri modi. La ricerca di interpolazione ha previsto che il runtime O (log log n) trovi un numero in un array ordinato, ma l’analisi è abbastanza coinvolta. In definitiva, l’analisi funziona mostrando che il numero di iterazioni è uguale al numero k tale che n2-k ≤ 2, per il quale log log n è la soluzione corretta. Alcuni algoritmi, come l’algoritmo MST Cheriton-Tarjan, arrivano a un runtime che coinvolge O(log log n) risolvendo un complesso problema di ottimizzazione vincolata.

Spero che questo aiuti!

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.