Intuition algorithmique pour la complexité logarithmique

Je pense avoir une compréhension raisonnable des complexités telles que , et .Θ ( n ) Θ ( n 2$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$

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$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$

Existe-t-il un moyen intuitif similaire de saisir autrement que de savoir qu'il se situe quelque part entre et ?O ( 1 ) Θ ( n $\Theta(\log n)$$\mathcal{O}(1)$$\Theta(n)$

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.$\Theta(\log n)$$\mathcal{O}(\log n)$

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.$32$$5$$128 = 2^7$$7$$1024 = 2^{10}$$10$

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.$n$$2^n$$\log_2 2^{10} = 10$

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

• devient la racine de l'arbre$\Theta(1)$
• est une promenade de la racine à la feuille$\Theta(\log n)$
• parcourt tousnoeuds de l'arbre$\Theta(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.$\Theta(n^2)$
• - généralisation de ce qui précède pour tout sous-ensemble de k nœuds (pour une constante k )$\Theta(n^k)$$k$$k$
• 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.$\Theta(2^n)$$k=1,2, \ldots, n$

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(\log n)$$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(\log n)$$O(\log n)$$O(\log n)$$\log n$

Pensez à l'algorithme pour convertir le nombre décimal en binaire$n$

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

Cette whileboucle exécute fois.$\log(n)$

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)$$1$$n$$1$$n$$\log(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 :)).$100$$2^{100}$$2^{100}$$2$$100$$100$$2^{100}$$2^{100}$$2^{100}$

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 .$100$$2^{100}$$100$$2^{100}$$2$$100$$2^{100}$$100$$2^{100}$$\log(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 $A$$B$$C$$B$$C$$A$$C$$D$$C$$A$$D$? 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 .$2\cdot 3\cdot 4$$24$$2^{10}$$1024$$2^{10}$$10$$10$$2^{10}$$10$$1024$

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.$\log_2(n)$$n$$n$$2^n$$2$$\log_b(n)$$b$$b$$n$$\log(n)$$n$$n$

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$

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(\log n)$$x$

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

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 ) .$\Theta(\lg^k n)$$\Theta(\lg^{k+1} n)$

$\Theta(1)$$\lg n$

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

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