Théorème principal avancé pour la récursion diviser pour régner

Divide and Conquer est un algorithme basé sur la décomposition récursive d'un problème en plusieurs sous-problèmes de type similaire, et ces sous-problèmes peuvent être facilement résolus.

Exemple

Prenons un exemple pour comprendre plus en profondeur la technique diviser pour régner -

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

Combinez les résultats de tous les sous-problèmes et renvoyons la solution au problème d'origine.

Explication − Dans le problème ci-dessus, le L'ensemble de problèmes doit être subdivisé en sous-problèmes plus petits qui peuvent être résolus facilement.

Le théorème des maîtres pour diviser pour mieux régner est un théorème d'analyse qui peut être utilisé pour déterminer une valeur grande-0 pour les algorithmes de relations récursives. le temps requis par l'algorithme et représentez-le sous forme de notation asymptotique.

Exemple de valeur d'exécution du problème dans l'exemple ci-dessus −

T(n) = f(n) + m.T(n/p)

Pour la plupart des algorithmes récursifs, vous pourrez trouver la complexité temporelle pour l'algorithme en utilisant le théorème de maître, mais dans certains cas, le théorème de maître peut ne pas être applicable. Ce sont les cas dans lesquels le théorème de maître n'est pas applicable lorsque le problème T(n) n'est pas monotone, par exemple, T(n) = péché. n . La fonction problème f(n) n'est pas un polynôme.

Comme le théorème principal pour trouver la complexité temporelle n'est pas très efficace dans ces cas, un théorème principal avancé pour la récurrence récursive a été conçu pour gérer le problème de récurrence du. form −

T(n) = aT(n/b) + ø((n^k)logpn)

où n est la taille du problème.

a = nombre de sous-problèmes dans la récursion, a > 0

n/b = taille de chaque sous-problème b > 1, k >= 0, p est un nombre réel.

Pour résoudre ce type de problème nous utiliserons la solution suivante :

• Si a > b_k, alors T(n) = ∅ (nlogba)
• Si a = b_k, alors
  • Si p > -1, alors T(n) = ∅(nlogba log^p+1n)
  • Si p = -1, alors T(n) = ∅(nlog_ba loglogn)
  • Si p ba)
• Si a k, alors
  • Si p > _klog_pn)
  • Si p

En utilisant l'algorithme maître avancé, nous calculerons la complexité de certains algorithmes −

Recherche binaire − t(n) = θ(logn)

Tri par fusion − T(n) = θ(nlogn)

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!