Notation Big O : Comprendre la complexité temporelle à l'aide d'organigrammes

Je recommande fortement l'article d'Edison sur la complexité Big-O en JavaScript. C'est l'article le plus convivial que j'ai vu sur le sujet.

Article n'est plus disponible

Je vais reprendre ici les points d'Edison en visualisant la complexité temporelle de Big-O avec des organigrammes.

O log(n)

Temps logarithmique

La façon dont je comprends visuellement la complexité temporelle est de regarder l'itérateur, i*2 par exemple, et de regarder le nombre de boucles de la fonction.

Sur)

Temps linéaire



Le temps linéaire et le temps logarithmique se ressemblent mais le résultat est différent en raison des conditions de la boucle. exampleLogarithmic(100) renverra 1, 2, 4, 8, 16, 32, 64, alors que exampleLinear(100) parcourt simplement tous les entiers positifs inférieurs à 100.

O(n^2)

Temps quadratique



Le nombre de boucles coïncide avec l'exposant auquel n est élevé. Vous pouvez littéralement voir la fonction s'agrandir à mesure que la complexité temporelle augmente.

O(n^3)

Temps Cube



Ce n’est pas la seule façon de comprendre la complexité temporelle, mais il est très utile de voir littéralement la fonction s’allonger à mesure que la complexité temporelle augmente. Parfois, du code écrit en noir et blanc

 les blocs ne font pas comprendre le message aux apprenants visuels.


Maintenant, faisons un quiz. Quelle est la complexité temporelle de cette fonction ?

Faites votre devinette...





C'est linéaire ! Je peux le dire car il y a une boucle et l'itérateur ne fait pas sauter la boucle sur des entiers.

Quelle est la complexité temporelle de cette fonction ?





Ne doutez pas de vous. Bien que cela soit un peu différent des premiers exemples, sa complexité temporelle est linéaire.

Quelle est la complexité temporelle de cette fonction ?





Vous pouvez voir un modèle ici. C'est linéaire !
Maintenant, si vous avez suivi mon raisonnement logique, cela peut être une question piège :




J'ai dit que le nombre de boucles désigné par l'exposant n est élevé à. Alors pourquoi cela a-t-il une complexité temporelle linéaire et non quadratique ?

Cela aurait une complexité temporelle quadratique s'il montrait une boucle for à l'intérieur d'une autre boucle for. Cependant, une boucle for qui s'exécute après une autre boucle for n'a pas une complexité temporelle quadratique mais plutôt linéaire.

D'accord, alors quelle est la complexité temporelle de cette fonction ?





Il n'y a rien de compliqué ici. Cela a une complexité temporelle quadratique.

Maintenant, pour votre dernière question - une question qui remet en question toutes les autres questions - quelle est la complexité temporelle de cette fonction ?





J'espère que vous examinez les conditions de la boucle for ainsi que le nombre de boucles. Cela a une complexité temporelle quadratique en raison de la condition de boucle i

J'ai généré les images de cet article avec mon application, dont j'ai décrit le processus de développement dans un autre article :

[


  
  
  Comment obtenir 100 sur Lighthouse



  
  
  Ender Minyard ・ 30 août 2020 ・ 2 min de lecture



  
  
  webperf#vitesse#javascript#webdev


](/ender_minyard/how-i-got-100-on-lighthouse-2icd)


          

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!