Qu'est-ce que O(log* N)?

Question

Qu'est - O(log* N)? Je l'ai trouvé en ligne, avec pas de description.

edit: je sais grand-Oh, le journal* a la question

Answer 1

O( log* N ) est "logarithme itéré":

En informatique, le logarithme itéré de n, écrit le journal* n (l'habitude de lire "journal d'étoiles"), est le nombre de fois que la fonction logarithme doit être appliqué de manière itérative avant que le résultat est inférieur ou égal à 1.

Answer 2

journal* (n)- "journal des Étoiles n" aussi connu comme "logarithme Itéré"

En termes simples, vous pouvez supposer log* (n)= log(log(log(.....(journal* (n))))

journal* (n) est très puissant.

Exemple:

1) Journal* (n)=5 où n= Nombre d'atomes dans l'univers

2) l'Arbre à Colorier à l'aide de 3 couleurs peut être fait dans le journal*(n), tandis que la coloration de l'Arbre 2 couleurs sont assez, mais la complexité O(n) alors.

3) Trouver la triangulation de Delaunay d'un ensemble de points de connaître le Euclidienne minimum spanning tree: aléatoire O(n log* n) fois.

Answer 3

Il indique comment un algorithme effectue: la Notation Grand O (faites défiler vers le bas pour "les Commandes de fonctions communes" et vous verrez un grand nombre d'échantillons, y compris les vôtres)