Comment savoir quand Big O est Logarithmique?

Question

Ma question provient de la poste "Plain English Explanation of Big O". Je ne connais pas la signification exacte de la complexité logarithmique. Je sais que je peux faire une régression entre le temps et le nombre d'opérations et calculer la valeur X-carré, et déterminer ainsi la complexité. Cependant, je veux connaître une méthode pour le déterminer rapidement sur papier.

Comment déterminez-vous la complexité logarithmique? Y a-t-il de bons repères?

Answer 1

Vous ne savez pas si c'est ce que vous voulez dire, mais ... la complexité logarithmique survient généralement lorsque vous travaillez avec une structure de données étalée comme un arbre binaire équilibré, qui contient 1 nœud à la racine, 2 enfants, 4 petits-enfants, 8 arrière-petits-enfants, etc. Au fond, à chaque niveau, le nombre de nœuds est multiplié par un facteur (2), mais un seul d'entre eux est impliqué dans l'itération. Ou comme un autre exemple, une boucle dans laquelle l'indice double à chaque étape:

for (int i = 1; i < N; i *= 2) { ... } 

Des choses comme ça sont les signatures de complexité logarithmique.

Answer 2

Master theorem fonctionne habituellement.

Answer 3

Pas rigoureux, mais si vous avez un algorithme qui divise essentiellement le travail à faire de moitié à chaque itération, alors vous avez une complexité logarithmique. L'exemple classique est la recherche binaire.

Answer 4

Si vous voulez juste savoir sur Big Oh logarithmique, soyez à l'affût de quand vos données sont coupées dans la moitié de chaque étape de la récurrence. Ceci est dû au fait que si vous traitez des données qui sont 1/2 aussi grandes que l'étape précédente, il s'agit d'une série infinie.

Answer 5

Voici une autre façon de le dire. Supposons que votre algorithme soit linéaire en nombre de chiffres dans la taille du problème.

Ainsi, vous avez peut-être un nouvel algorithme pour factoriser un grand nombre, que vous pouvez montrer comme étant linéaire dans le nombre de chiffres. Un nombre à 20 chiffres prend ainsi deux fois plus de temps qu'un facteur à 10 chiffres en utilisant votre algorithme. Cela aurait une complexité de log. (Et cela vaut quelque chose pour l'inventeur.)

La sectionnement a le même comportement. Il faut environ 10 étapes de bissection pour réduire la longueur de l'intervalle d'un facteur de 1024 = 2^10, mais seulement 20 pas couperont l'intervalle d'un facteur de 2^20.

La complexité du journal ne signifie pas toujours qu'un algorithme est rapide sur tous les problèmes. Le facteur linéaire devant l'O (log (n)) peut être important. Donc votre algorithme peut être terrible sur de petits problèmes, ne pas devenir utile jusqu'à ce que la taille du problème soit sensiblement grande que d'autres algorithmes meurent d'une mort exponentielle (ou polynomiale).