Explication détaillée de l'utilisation de la programmation dynamique JS

Cette fois, je vais vous apporter une explication détaillée de l'utilisation de la programmation dynamique JS. Quelles sont les précautions lors de l'utilisation de la programmation dynamique JS. Voici des cas pratiques, jetons un coup d'œil.

En fait, dans notre développement front-end, peu d'algorithmes avancés sont utilisés. Dans la plupart des cas, les instructions if, for , les instructions swith, etc. résolu. Si c'est un peu plus compliqué, vous pourriez penser à utiliser la récursivité pour le résoudre.

Mais il convient de noter que la récursivité est simple à écrire, mais en fait elle n'est pas très efficace dans son exécution.

Regardons à nouveau l'algorithme de programmation dynamique :

Les solutions de programmation dynamique commencent par la base, résolvant tous les petits problèmes, puis les combinent en une solution holistique pour résoudre l'ensemble du gros problème.

Exemples (calcul des nombres de Fibonacci)

La séquence de Fibonacci fait référence à une séquence de nombres 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946. , 17711, 28657, 46368.....

Cette séquence commence par l'élément 3, et chaque élément est égal à la somme des deux éléments précédents.

Pour cette séquence, vous pouvez utiliser une fonction récursive pour calculer la nième valeur de l'élément

// 斐波那契数列
function recurFib(n) {
    if(n ");
      return recurFib(n-1)+recurFib(n-2)
    }
}

Il s'agit en effet d'un code très concis. Le code commenté ci-dessus est utilisé pour afficher combien de fois la fonction doit être exécutée lorsque n =. Cependant, une personne avisée peut voir en un coup d'œil que le nombre d'exécutions augmentera à mesure que n augmente. . Croissance très effrayante.

Lorsque n=5, l'arbre de récursivité est devenu très grand... On peut prédire que lorsque n=10, voire n=100...

Après avoir compris la différence d'efficacité d'exécution des fonctions récursives, regardons comment la programmation dynamique est effectuée

function dynFib(n) {
  let val = [];
  for(let i = 0; i <p style="text-align: left;">
Le résultat intermédiaire est enregistré dans le tableau val. Si le nombre de Fibonacci à calculer est 1 ou 2, alors l'instruction if renverra 1. Sinon, les valeurs 1 et 2 seront stockées aux positions 1 et 2 du tableau val. </p><p style="text-align: left;">
La boucle passera de 3 aux paramètres d'entrée et affectera chaque élément du tableau à la somme des deux premiers éléments. Lorsque la boucle se termine, la valeur du dernier élément du tableau est la valeur finale de Fibonacci calculée. être utilisé comme valeur de retour <a href="http://www.php.cn/code/6029.html" target="_blank"> de la fonction </a>. </p><p style="text-align: left;">
Ensuite, vous pouvez écrire une fonction de test simple pour comparer le temps d’exécution des deux. </p><pre class="brush:php;toolbar:false">// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

Exécution de la fonction d'impression

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

Les résultats sont les suivants :

Enfin, vous avez peut-être réalisé qu'il est possible de calculer la séquence de Fibonacci sans utiliser de tableaux en utilisant une approche itérative.

La raison pour laquelle les tableaux sont nécessaires est que les algorithmes de programmation dynamique doivent généralement enregistrer les résultats intermédiaires.

Ce qui suit est la version itérative de la signification de la fonction Fibonacci

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i <p style="text-align: left;">
Bien entendu, l’efficacité de cette version itérative est la même que celle de la version tableau. </p><p>Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php ! </p><p>Lecture recommandée : </p><p><a href="http://www.php.cn/js-tutorial-392657.html" target="_blank">Comment utiliser l'entrée et la sortie Angular4</a><br></p><p><a href="http://www.php.cn/js-tutorial-392661.html" target="_blank">Comment utiliser les autorisations utilisateur dans Vue2.0</a><br></p><p style="text-align: left;">
</p><!--content end-->

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!