Intuition algorithmique pour la complexité logarithmique

60

Je pense avoir une compréhension raisonnable des complexités telles que , et .Θ ( n ) Θ ( n 2 )O(1)Θ(n)Θ(n2)

En termes de liste, est une recherche constante, donc il ne fait que prendre la tête de la liste. est l'endroit où je parcourrais toute la liste, et parcourait la liste une fois pour chaque élément de la liste.Θ ( n ) Θ ( n 2 )O(1)Θ(n)Θ(n2)

Existe-t-il un moyen intuitif similaire de saisir autrement que de savoir qu'il se situe quelque part entre et ?O ( 1 ) Θ ( n )Θ(logn)O(1)Θ(n)

Khanzor
la source
8
log n est pour "chercher": pensez recherche binaire
Suresh
2
Utiliser O pour poser cette question est incorrect, car cela ne représente qu'une limite supérieure. Par exemple, le temps constant est O(logn) . θ serait plus approprié. Voir la méta question: meta.cs.stackexchange.com/questions/182/…
Aryabhata
1
Plus d'informations sur SO: que signifie exactement O(logn) ? .
Ran G.
Une petite remarque: dans les réglages classiques de Turing Machine, tous les algorithmes sont Ω(n) , car ils doivent lire chaque symbole de l’entrée au moins une fois. La recherche binaire peut être effectuée dans O(logn) car nous avons la promesse que la liste est triée, par exemple.
Chazisop
1
Une contribution tardive: par définition, le logarithme de base d'un nombre n est simplement le nombre de fois que vous multipliez b par lui-même pour obtenir n . b l = nbnbn . Par exemple, 2 3 = 8bl=nl=logb(n) . Donc, si vous avez un nombre n et que vous voulez savoir ce que l o g b ( n ) = ? continuez simplement à diviser par b jusqu'à atteindre un 1 (en supposant que n est une puissance de b pour simplifier). Le nombre de divisions est égal à l o g b ( n ) . Les algorithmes présentant ce comportement de division ont des temps d'exécution dans O ( l o g23=8log2(8)=3nlogb(n)=?b1nblogb(n) . O(log(n))
Saadtaame

Réponses:

54

Le complexité est généralement liée à subdivision. En utilisant des listes comme exemple, imaginez une liste dont les éléments sont triés. Vous pouvez rechercher dans cette liste en temps O ( log n ) - vous n’avez pas besoin de consulter chaque élément en raison de la nature triée de la liste.Θ(logn)O(logn)

Si vous regardez l'élément au milieu de la liste et le comparez à l'élément que vous recherchez, vous pouvez immédiatement dire s'il se trouve dans la moitié gauche ou droite du tableau. Ensuite, vous pouvez simplement prendre cette moitié et répéter la procédure jusqu'à ce que vous la trouviez ou accéder à une liste avec 1 élément que vous comparez trivialement.

Vous pouvez voir que la liste réduit de moitié chaque étape. Cela signifie que si vous obtenez une liste de longueur , le nombre maximal d'étapes dont vous avez besoin pour atteindre une liste à un élément est de 5 . Si vous avez une liste de 128 = 2 7 éléments, vous n'avez besoin que de 7 étapes. Pour une liste de 1024 = 2 10, vous n'avez besoin que de 10 étapes, etc.325128=2771024=21010

Comme vous pouvez le constater, l'exposant dans 2 n indique toujours le nombre d'étapes nécessaires. Le logarithme est utilisé pour "extraire" exactement ce nombre d'exposants, par exemple log 2 2 10 = 10 . Il généralise également la liste des longueurs qui ne sont pas des puissances de deux.n2nlog2210=10

Karel Petranek
la source
4
Il est à noter que ceci n’est O(log n)valable que si la liste a un accès aléatoire à temps constant. Sur des implémentations de listes plus typiques (listes chaînées) c'estO(n log n)
asm
1
La recherche binaire ne fonctionne pas sur les listes faute de pointeurs. cela se fait généralement sur des tableaux.
Raphaël
La recherche binaire fonctionne très bien sur les listes. C'est tout à fait inutile car il est beaucoup plus compliqué que nécessaire / utile / pratique.
Anton
@AndrewMyers La recherche d'une liste chaînée est plus précise. O(n)
phant0m
1
@ phant0m Oui, il m'a fallu un peu de temps pour comprendre que cela suppose que vous vous déplacez de la position actuelle au lieu de partir du début à chaque fois.
asm
38

En termes d’arbres (équilibrés) (disons un arbre binaire, tous les sont en base 2):log

  • devient la racine de l'arbreΘ(1)
  • est une promenade de la racine à la feuilleΘ(logn)
  • parcourt tousnoeuds de l'arbreΘ(n)
  • correspond aux actions sur tous les sous-ensembles de deux nœuds de l’arborescence, par exemple le nombre de chemins différents entre deux nœuds quelconques.Θ(n2)
  • - généralisation de ce qui précède pour tout sous-ensemble de k nœuds (pour une constante k )Θ(nk)kk
  • est une action sur tous les sous-ensembles possibles de nœuds (sous-ensembles de toutes les tailles possibles, c'est-à-dire, k = 1 , 2 , , n .). Par exemple, le nombre desous-arbres différentsde l'arbre.Θ(2n)k=1,2,,n
A sonné.
la source
5
Pour ajouter à cela, l'intuition pour provient de deux choses: 1.) La récurrence T ( n ) = T ( Θ(loglogn)et 2.) Recherche binaire sur un objet de taillelog(n),c’est-à-dire une recherche binaire sur la hauteur de l’arbre. T(n)=T((n))+1log(n)
mcorley
17

Pour que soit possible, vous devez être en mesure de réduire la taille du problème proportionnellement d'une quantité arbitraire par rapport à n avec une opération à temps constant.O(logn)n

Par exemple, dans le cas d'une recherche binaire, vous pouvez réduire de moitié la taille du problème à chaque opération de comparaison.

Maintenant, devez-vous réduire la taille du problème de moitié, en fait non. Un algorithme est même s'il peut réduire l'espace de recherche de problème de 0,0001%, tant que le pourcentage et l'opération utilisés pour réduire la taille du problème restent constants, il s'agit d'un algorithme O ( log n ) , ce ne sera pas un algorithme rapide, mais ça reste O ( log n ) avec une très grande constante. (En supposant que nous parlons de log n avec un log de base 2)O(logn)O(logn)O(logn)logn

Ken Li
la source
1
Que serait-il si le «montant de réduction» n'était pas constant?
Svish
@Svish Si vous pouviez réduire le problème à un taux positif, il s'agirait toujours d'un algorithme , bien que ce ne soit probablement plus un lien étroit. Le taux négatif est difficile à dire. On a supposé que la réponse serait plutôt simple dans ce cas, puisque cette question a son mérite propre, vous êtes plus que bienvenu si vous le posez comme une question à part entière. O(logn)
Ken Li
Oui, je voulais dire que l'espace de recherche de problèmes a toujours diminué, mais pas nécessairement à un taux constant. Je pensais juste à votre "tant que le pourcentage et l’opération utilisée pour réduire la taille du problème restent constants, c’est un algorithme O (log n)"; si elle avait un nom différent si le pourcentage n'était pas constant.
Svish
8

Pensez à l'algorithme pour convertir le nombre décimal en binairen

while n != 0:
   print n%2, 
   n = n/2

Cette whileboucle exécute fois.log(n)

Pratik Deoghare
la source
1
Certes, le programme boucle boucle n fois, mais généralement quand on parle de complexité O ( f ( s ) ) , s est la taille de votre entrée. Ici, la taille de votre entrée est déjà s = log n , je dirais donc que ce programme est uniquement linéaire (en O ( s ) )lognO(f(s))ss=lognO(s)
jmad
@jmad droit. Mais cet exemple vous donne une intuition dans log (n).
Pratik Deoghare
@jmad J'aurais aussi pu utiliser un algorithme pour générer des nombres aléatoires, mais je le voulais aussi simple que possible.
Pratik Deoghare
8

Oui, est compris entre 1 et n , mais il est plus proche de 1 que n . Qu'est-ce que log ( n ) ? La fonction log est la fonction inverse de l'exponentation. Permettez-moi de commencer par l'exposé et vous devriez avoir une meilleure idée de ce qu'est le logarithme.log(n)1n1nlog(n)

Considérons deux nombres, et 2 100 . 2 100 est 2 multiplié avec lui-même 100 fois. Vous pouvez, avec quelques efforts, compter 100 nombres, mais pouvez-vous compter 2 100 ? Je parie que tu ne peux pas. Pourquoi? 2 100 est un nombre tellement grand qu'il est supérieur au nombre d'atomes de l'univers. Réfléchissez-y un instant. C'est un nombre tellement énorme qu'il vous permet de donner un nom (nombre) à chaque atome. Et le nombre d'atomes dans votre ongle est probablement de l'ordre de milliards. 2 100 devrait suffire à quiconque (jeu de mots voulu :)).100210021002100100210021002100

Maintenant, entre les deux nombres, et 2 100 , 100 est le logarithme de 2 100 (en base 2 ). 100 est comparativement un nombre aussi petit que 2 100 . Tout le monde devrait avoir 100 articles différents chez eux. Mais, 2 100 est assez bon pour l'univers. Pensez à la maison contre l'univers en pensant à log ( n ) et n .10021001002100210021001002100log(n)n

D'où proviennent l'exponentation et les logarithmes? Pourquoi ont-ils tant d'intérêt pour l'informatique? Vous ne le remarquerez peut-être pas, mais l'exposant est partout. Avez-vous payé des intérêts sur votre carte de crédit? Vous venez de payer un univers pour votre maison (pas si mal, mais la courbe convient). J'aime penser que l'exponentation vient de la règle du produit, mais les autres sont les bienvenus pour donner plus d'exemples. Quelle est la règle du produit, vous pouvez demander; Et je vais répondre.

Supposons que vous avez deux villes et B et qu’il existe deux manières de les séparer. Quel est le nombre de chemins entre eux? Deux. C'est trivial. Maintenant, disons qu'il y a une autre ville C et que vous pouvez passer de B à C de trois manières. Combien de chemins y a-t-il entre A et C maintenant? Six, non? Comment as-tu eu ça? Les avez-vous comptés? Ou les avez-vous multiplié? De toute façon, il est facile de voir que les deux manières donnent un résultat similaire. Maintenant, si vous ajoutez une ville D accessible de C de quatre manières, combien y a-t-il de manières entre A et DABCBCACDCAD? Comptez si vous ne me faites pas confiance, mais il est égal à qui est 24 . Maintenant, s’il ya dix villes et deux chemins d’une ville à l’autre, ils sont disposés en ligne droite. Combien de chemins y a-t-il du début à la fin? Multiplie-les si tu ne me fais pas confiance, mais je te dirai qu'il y en a 2 10 , soit 1024 . Voir que 2 10 est un résultat exponentiel de 10 et 10 est le logarithme de 2 10 . 10 est un petit nombre comparé à 1024 .2342421010242101010210101024

La fonction logarithme est à n ce que n est à 2 n (notez que 2 est la base du logarithme). Si vous multipliez le journal b ( n ) avec lui-même b fois (notez que b est la base du logarithme), vous obtenez n . log ( n ) est si petit, si petit comparé à n , que c'est la taille de votre maison où n est la taille de l'univers.log2(n)nn2n2logb(n)bbnlog(n)nn

Sur une note pratique, les fonctions fonctionnent de manière très similaire aux fonctions constantes. Ils grandissent avec n , mais ils grandissent très lentement. Si vous avez optimisé l'exécution d'un programme en temps logarithmique prenant un jour avant, vous l'exécuterez probablement dans l'ordre des minutes. Vérifiez par vous-même les problèmes sur Project Euler.log(n)n

Ravi
la source
3
Bien que bien écrit, cette réponse ne contient pratiquement aucune information à part "le est vraiment petit". log(n)
Raphaël
3
J'essayais de donner une intuition sur sa petite taille.
Ravi
5

Pour continuer votre thème, revient à deviner de façon répétée où x se trouve dans la liste et à se faire dire «plus haut» ou «plus bas» (en termes d’index).O(logn)x

Cela dépend toujours de la taille de la liste, mais il vous suffit de visiter une fraction des éléments.

dépêche
la source
4

Si nous avons un diviser pour régner , et nous faisons un seul appel récursif pour un sous - problème, et il est le deuxième cas dans le théorème maître , à savoir la complexité temporelle de la partie non récurrente est , le la complexité de l'algorithme sera Θ ( lg k + 1 n ) .Θ(lgkn)Θ(lgk+1n)

Θ(1)lgn

L' algorithme de recherche binaire est l'exemple classique.

Kaveh
la source
1

L'intuition est le nombre de fois que vous pouvez diviser par deux un nombre, disons n, avant qu'il ne soit réduit à 1, c'est O (lg n).

Pour visualiser, essayez de le dessiner comme un arbre binaire et comptez le nombre de niveaux en résolvant cette progression géométrique.

2^0+2^1+...+2^h = n
utilisateur1234
la source
lognn