Qu'est-ce que O (log (log (n)))) - moyenne compétitive?

Question

Je traversais des structures de données et j'ai remarqué cela comme une complexité temporelle:      O (log (log (n)))) -. Compétitive

Je lis c'était compétitif constant le rapport du temps prévu / temps optimal. Mais qu'est-ce que cela signifie d'avoir un ensemble compétitif?

Answer 1

algorithme en ligne est celui qui ne connaît pas ses entrées à l'avance, et doit « réagir » (dans un sens) aux entrées imprévisibles. En revanche, les algorithmes hors ligne sont ceux qui connaissent toutes ses entrées à l'avance.

Analyse concurrentielle compare les performances d'un algorithme en ligne optimale à un algorithme en mode hors connexion optimale. Ainsi, signifie k compétitif qu'il existe un algorithme en ligne qui effectue la plupart des k-fois pire qu'un algorithme en ligne. Ainsi, O (lglgn) concurrentiel signifie que l'algorithme optimal en mode hors connexion effectue au plus lglgn (fois) une constante fois pire que l'algorithme en ligne optimale.

---

Le terme « k-compétitif » peut être considéré de la même manière que le terme « k-approximation ». A k-approximation signifie que l'algorithme d'approximation effectue au plus k fois pire que l'algorithme optimal.

Answer 2

Cette peut faire la lumière sur votre question.
À partir du lien ci-dessus:

  

Soit A tout algorithme de BST, définir   A (S) comme le coût de l'exécution   séquence S et OPT (S, A) en tant que   coût minimal pour effectuer la séquence   S. Un algorithme A est T-concurrentiel si   pour toutes les séquences possibles S, A (S) <=   T * OPT (S, A) + O (m, n).