Comment savoir quand Big O est logarithmiques?

Question

Ma question se pose du poste "Plain English Explication de 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 de calculer la valeur au carré X, et de déterminer si la complexité. Cependant, je veux savoir une méthode pour déterminer rapidement sur le papier.

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

Answer 1

Je ne sais pas si cela est ce que vous voulez dire, mais ... la complexité logarithmique se produit généralement lorsque vous travaillez avec une structure de données étalé comme un arbre binaire équilibré, qui contient 1 nœud à la racine, 2 enfants, 4 petits-enfants, 8 arrière-petits-enfants, etc. en fait à chaque niveau le nombre de noeuds est multiplié par un facteur (2), mais encore que l'un de ceux qui est impliqué dans l'itération. Ou comme autre exemple, une boucle dans laquelle l'indice de double à chaque étape:

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

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

Answer 2

Non rigoureux, mais vous avez un algorithme qui est essentiellement diviser le travail nécessaire à faire de moitié à chaque itération, alors vous avez la complexité logarithmique. L'exemple classique est la recherche binaire.

Answer 3

théorème de maître fonctionne habituellement.

Answer 4

Si vous voulez juste savoir logarithmique Big Oh, être à l'affût de vos données sont coupé en deux à chaque étape de la récurrence.

En effet, si vous traitez des données est aussi grand que 1/2 de l'étape précédente, il est une série infinie.

Answer 5

Voici une autre façon de le dire.

Supposons que votre algorithme est linéaire dans le nombre de chiffres de la taille du problème. Alors, peut-être vous avez un nouvel algorithme de factoriser un grand nombre, que vous pouvez montrer à linéaire du nombre de chiffres. Un numéro de 20 chiffres prend ainsi deux fois plus de temps pour tenir un numéro à 10 chiffres en utilisant votre algorithme. Cela aurait la complexité du journal. (Et ce serait quelque chose d'intéressant pour l'inventeur.)

Bisection a le même comportement. Il faut environ 10 étapes de bissection pour couper la longueur de l'intervalle par un facteur de 1 024 = 2 ^ 10, mais seulement 20 mesures permettra de réduire l'intervalle d'un facteur 2 ^ 20.

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