Que signifie "log *"?

Question

Je suis tombé sur le terme O(log* N) dans un livre que je lis sur les structures de données. Que signifie log*? Je ne peux pas find it on Google, et WolframAlpha doesn't understand it either.

Answer 1

C'est un logarithme itéré. Voir here pour une description de beaucoup de complexités temporelles différentes, et here pour plus de détails sur le logarithme itératif lui-même. Le logarithme itératif est le nombre de fois que le logarithme doit être appliqué avant que le résultat ne devienne un ou moins.

Answer 2

Il s'appelle iterated logarithm function. C'est une fonction qui grandit très lentement. Par exemple:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5/note que (2^65536) est beaucoup plus grand que le nombre d'atomes dans l'univers observable/

Ou dans le cas de Big O, il pourrait être considéré comme un temps constant.

Answer 3

log * (n) - "log étoile n" comme connu sous le nom "logarithme itéré"

En simple mot vous pouvez supposer log * (n) = log (log (log (..... (log * (n))))

log * (n) est très puissant

. Exemple:

1) log * (n) = 5 où n = nombre d'atomes dans l'univers

2) Tree Coloring en utilisant 3 couleurs peut être fait en log * (n) Coloriage Arbre 2 couleurs suffisent mais la complexité sera alors O (n).

3) Trouver la triangulation de Delaunay d'un ensemble de points connaissant le spanning tree minimal euclidien: temps O (n log * n) randomisé.

J'espère que vous pouvez visualiser Log * (n) comme celui-ci sur WolframAlpha Check here

Answer 4

journal * est le nombre de fois que vous devez appliquer la fonction journal jusqu'à une valeur inférieure ou égale à 1. Par exemple: log * (16) = 3, parce que log (log (log (16))) = 1.

Pour des raisons pratiques, vous pouvez le traiter comme une constante , parce que cette fonction se développe très lentement.