Stavo attraversando alcune strutture dati e ho notato che questa era una complessità temporale: O (log (log (n)))) - competitivo.Cosa significa O (log (log (n)))) - competitivo?
Ho letto che costante-competitivo era il rapporto tra il tempo previsto/tempo ottimale. Ma cosa significa avere un set competitivo?
L'algoritmo online è uno che non conosce i suoi ingressi in anticipo e deve "reagire" (in un certo senso) a input imprevedibili. Al contrario, gli algoritmi offline sono quelli che conoscono tutti i suoi input in anticipo.
L'analisi competitiva confronta le prestazioni di un algoritmo online ottimale con un algoritmo offline ottimale. Pertanto, k-competitive significa che esiste un algoritmo offline che esegue al massimo k-volte peggio di un algoritmo online. Quindi, O (lglgn) competitivo significa che l'algoritmo offline ottimale esegue al massimo lglgn (volte una costante) volte peggiore dell'algoritmo online ottimale.
Il termine "k-competitivo" può essere pensato allo stesso modo del termine "k-approssimazione". Una k-approssimazione significa che l'algoritmo di approssimazione esegue al massimo k volte peggio dell'algoritmo ottimale.
This può far luce sulla tua domanda.
Dal link sopra:
Sia A un qualsiasi algoritmo BST, definire A (S) come costo di esecuzione sequenza S e OPT (S, A) come il costo minimo per eseguire la sequenza S. Un algoritmo A è competitivo T se per tutte le sequenze possibili S, A (S) < = T * OPT (S, A) + O (m, n).
Puoi migliorare la domanda? –
Puoi migliorarlo almeno di O (log (log (N)))? –